How to derive Catalan Number equation?

Question

I am looking for a way to derive the Catalan Number equation: $$ C_n = \frac{1}{n+1}\binom{2n}{n} $$ from: $$ C_0 = 1,\qquad C_{n+1}=\sum_{i=0}^{n} C_i\, C_{n-i}\,.$$

Answer 1

Let $$ f(z) = \sum_{n\geq 0} C_n z^n. $$ The recurrence formula gives: $$ [x^n]\,\frac{f(z)-1}{z}=[x^{n+1}]\,f(z)=C_{n+1}=\sum_{i=0}^{n}C_i C_{n-i} = [x^n]\,f(z)^2 $$ hence $$ f(z)-1 = z\,f(z)^2 $$ leads to: $$ f(z) = \frac{1-\sqrt{1-4z}}{2z}.$$ Now it is sufficient to use the binomial theorem to get the Taylor series of $\sqrt{1-z}$ in a neighbourhood of zero in terms of the central binomial coefficients, then manipulate such a series to compute the Taylor series of $f(z)$ and state: $$C_n = \frac{1}{n+1}\binom{2n}{n}$$ as wanted.