Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
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.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

You want Catalan number

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.