0
$\begingroup$

Define a sequence $(C_n)$ by $C_0=1$, $C_1=1$, and $C_{n+1} = \sum_{r=0}^n C_r C_{n-r}$ for $n\geq 2$. What is the simplest explicit formula for $C_n$?

$\endgroup$

2 Answers 2

5
$\begingroup$

You want Catalan number

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Divye
    Nov 6, 2009 at 12:57
  • $\begingroup$ 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. $\endgroup$
    – user709
    Nov 6, 2009 at 13:13
3
$\begingroup$

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.

$\endgroup$

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