most recent 30 from http://mathoverflow.net 2013-05-19T07:58:39Z http://mathoverflow.net/feeds/question/4374 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4374/what-is-the-simplest-non-recursive-formulation-for-the-following-recursive-functi Divye 2009-11-06T12:40:25Z 2009-11-06T14:36:37Z

<pre><code>C(0) = 1 C(1) = 1 C(n+1) = Sigma(r, 0, n, C(r) x C(n-r)) </code></pre> <p>Where Sigma() means: Sigma(index var, lower bound, upper bound (inclusive), function(r)) I'm not familiar with standard Latex notation as I'm not a mathematician, so please ignore the sloppy presentation of the problem.</p>

http://mathoverflow.net/questions/4374/what-is-the-simplest-non-recursive-formulation-for-the-following-recursive-functi/4375#4375 Ho Chung Siu 2009-11-06T12:48:44Z 2009-11-06T12:48:44Z

<p>You want <a href="http://en.wikipedia.org/wiki/Catalan%5Fnumber" rel="nofollow">Catalan number</a></p>

http://mathoverflow.net/questions/4374/what-is-the-simplest-non-recursive-formulation-for-the-following-recursive-functi/4383#4383 Qiaochu Yuan 2009-11-06T14:36:37Z 2009-11-06T14:36:37Z

<p>In response to the comment to the other answer: the general technique is to write the recursion as a generating function identity. In this particular case, the identity is C(x) = 1 + x C(x)^2 and one can use the quadratic formula, then the generalized binomial theorem. More generally there are now powerful computer packages that can solve certain general classes of recursions and spit back hypergeometric series; the canonical reference here is <a href="http://www.math.upenn.edu/~wilf/AeqB.html" rel="nofollow">Petovsek, Wilf, and Zeilberger</a>. If you don't know much about generating functions, you might want to check out <a href="http://www.math.upenn.edu/~wilf/DownldGF.html" rel="nofollow">Wilf's "generatingfunctionology"</a> first.</p>