Question in proving a recurrence relation for Catalan numbers

Question

How to prove the recurrence relation for Catalan numbers, stating $$C_{n}=\sum_{i=0}^{n-1}C_{i}C_{n-1-i}$$ where we define $C_{0}$ as $1$?

Answer 1

That depends on your definition of Catalan number. If they are defined through the number of sub-diagonal paths in a $n\times n$ grid, by a nice symmetry argument (which can be seen as a consequence of Bertand's ballot problem too, see page 18 of my notes) we have $$ C_n \stackrel{\text{symmetry}}{=} \frac{1}{n+1}\binom{2n}{n}= \frac{2\cdot 4^n}{\pi(n+1)}\int_{0}^{\pi/2}\cos(x)^{2n}\,dx $$ by Cauchy's integral formula ($\binom{2n}{n}$ is the coefficient of $x^n$ in $(1+x)^{2n}$) or by Euler-De Moivre's identity $2\cos(\theta)=e^{i\theta}+e^{-i\theta}$ and the orthogonality relation $\int_{0}^{2\pi}e^{ni\theta}e^{-mi\theta}\,d\theta=2\pi\,\delta(m,n)$. In particular the associated generating function $$ f(x) = \sum_{n\geq 0} C_n x^n = \frac{2}{\pi}\int_{0}^{\pi/2}\sum_{n\geq 0}\frac{(4x)^n\left(\cos \theta\right)^{2n}}{n+1}\,d\theta=\frac{2}{\pi x}\int_{0}^{+\infty}-\log\left(1-\frac{4x}{1+t^2}\right)\,dt $$ fulfills $$ f(x) = \frac{1-\sqrt{1-4x}}{2x},\qquad \color{blue}{f(x)=1+x\cdot f(x)^2}. $$ By the Cauchy product of (Taylor) series. The blue identity implies $$ C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k} $$ as claimed. This can be proved in a direct combinatorial way, by considering any sub-diagonal path in a $(n+1)\times(n+1)$ grid and the first time it touches the diagonal after the start.

---

The blue identity is actually just an instance of a marvel in the realm of hypergeometric functions: $$\text{(Clausen's formula)}\qquad\phantom{}_2 F_1\left(a,b;a+b+\tfrac{1}{2}; x\right)^2 = \phantom{}_3 F_2\left(2a,a+b,2b;a+b+\tfrac{1}{2},2a+2b;x\right) $$ since $f(x)=\phantom{}_2 F_1\left(\frac{1}{2},1;2;4x\right)$.

Answer 2

Since as of this moment the original poster hasn't given us a definition, I propose flipping this around the following way: Of all the possible ways of defining the Catalan numbers, find the definition which leads most quickly to the recurrence relation. Of course, you are not allowed to use the recurrence relation itself as the definition! I propose the following solution. The $n^{th}$ Catalan number $C_n$ is defined as the number of rooted binary trees with $n$ internal nodes. (A rooted binary tree is a tree with a starting root node and where every node has 0 or 2 children nodes. Internal nodes have 2 children.) Then a rooted tree with $n+1$ internal nodes ($n \ge 0$) has an internal root node with i internal nodes on the left and $n-i$ on the right, so $C_i C_{n-i}$ possibilities. Do this for all i and add up the possibilities to get the recurrence relation. Anything simpler? I wonder...