# What is the simplest non-recursive formulation for the following recursive function?

C(0) = 1
C(1) = 1
C(n+1) = Sigma(r, 0, n, C(r) x C(n-r))


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.

-

## 2 Answers

You want Catalan number

-
How can the terms of such series be obtained in general given only the recursive representation? The product within the sigma causes difficulties in evaluation of the problem. –  Divye Nov 6 '09 at 12:57
I am not familiar with combinatorics at all, so perhaps others can give you a better answer. In my understanding, one common technique of finding the general term uses the generating function (the first proof in wiki). The product in this situation looks exactly like the coefficients of multiplication of two power series. This suggests that generating function could work. –  Ho Chung Siu Nov 6 '09 at 13:13

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 Petovsek, Wilf, and Zeilberger. If you don't know much about generating functions, you might want to check out Wilf's "generatingfunctionology" first.

-