I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number).

For $n=1$ this is true.

Assume it is true for $n=k$:

$$C_k = \sum_{i=0}^{k-1} C_iC_{k-i-1}$$

Now we just need to show that $$C_{k+1} = \sum_{i=0}^{k} C_iC_{k-i}$$

And here I'm stuck. I can't understand how to use our assumption.

Friendly reminder: $C_r = \frac{1}{r+1} {2r \choose r}$ for all $ 0\leq r$


There are many different definitions of the Catalan numbers that make different properties clearer. One is as the number of ways to parenthesize the product $x_1 x_2 \dots x_{n+1}$, which makes the relation you want to prove obvious. From that you can show that the generating function $\sum C_n x^n$ is the solution of a quadratic equation in $x$ and has a formula involving the square root of some function like $\frac{1}{1-x}$ (probably not exactly that, but similar). Then the binomial theorem for exponent $1/2$ tells you a formula for the generating function coefficients and shows this definition is equivalent to the numerical one.

To start from the definition at the end of the question, the formula for the numbers, and prove the recursion looks like a potentially complicated combinatorial problem. I don't think this is the way it would normally be done except for the sake of sport or its evil twin, student exercises.

  • $\begingroup$ Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction. $\endgroup$ – Oria Gruber Nov 19 '13 at 22:25
  • 2
    $\begingroup$ I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest. $\endgroup$ – zyx Nov 19 '13 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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