What is the simplest non-recursive formulation for the following recursive function? - MathOverflow 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 What is the simplest non-recursive formulation for the following recursive function? 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 Answer by Ho Chung Siu for What is the simplest non-recursive formulation for the following recursive function? 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 Answer by Qiaochu Yuan for What is the simplest non-recursive formulation for the following recursive function? 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>