Generating Functions - Main Theorem

The Catalan numbers appear in numerous combinatorial structures, and their generating function provides elegant derivations of both the recurrence and closed form.

Derivation from Recurrence:

The Catalan numbers satisfy $C_0 = 1$ and: $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k} \text{ for } n \geq 1$

This recurrence arises from decomposing binary trees: a tree with $n$ internal nodes has a root and two subtrees with $k$ and $n-1-k$ internal nodes respectively, summing over all $k$.

Let $C(x) = \sum_{n=0}^{\infty} C_n x^n$. The convolution in the recurrence suggests: $\sum_{n=1}^{\infty} C_n x^n = \sum_{n=1}^{\infty} \left(\sum_{k=0}^{n-1} C_k C_{n-1-k}\right) x^n$

The right side is $x \cdot C(x) \cdot C(x) = xC(x)^2$.

Therefore: $C(x) - C_0 = xC(x)^2$ $C(x) - 1 = xC(x)^2$ $xC(x)^2 - C(x) + 1 = 0$

Using the quadratic formula (treating $C(x)$ as the unknown): $C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$

Since $C(x)$ should have $C(0) = 1$ and be analytic at $x=0$, we need the negative sign (the positive sign gives $\infty$ at $x=0$): $C(x) = \frac{1 - \sqrt{1-4x}}{2x}$

Extracting the Coefficient:

We can expand $(1-4x)^{1/2}$ using the binomial series: $(1-4x)^{1/2} = \sum_{k=0}^{\infty} \binom{1/2}{k} (-4x)^k$

where $\binom{1/2}{k} = \frac{(1/2)(1/2-1)\cdots(1/2-k+1)}{k!} = \frac{(1/2)(-1/2)(-3/2)\cdots(3/2-k)}{k!}$.

After simplification: $\binom{1/2}{k} = \frac{(-1)^{k-1}}{2^{2k-1}k} \binom{2k-2}{k-1}$ for $k \geq 1$.

Substituting and comparing coefficients: $C_n = \frac{1}{n+1}\binom{2n}{n}$

This is the closed form for Catalan numbers. $\square$