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$
Best Answer
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.