# Combinatorics - Catalan numbers recursive function proof by induction help

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$

• What is your definition of Catalan's numbers? – Pedro Tamaroff Mar 3 '15 at 21:50
• – Doris Jan 27 at 20:03
• @PedroTamaroff I guess there is just one definition. Isn't it ?. Catalan Number. – Felix Marin Jan 30 at 6:18

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.