We interpret $C_n$ as counting Dyck paths: lattice paths from $(0,0)$ to $(2n,0)$ using steps $U = (1,1)$ (up) and $D = (1,-1)$ (down) that never go below the $x$-axis.

Step 1: Total paths without restriction. Any path from $(0,0)$ to $(2n,0)$ uses $n$ up steps and $n$ down steps. There are $\binom{2n}{n}$ such paths.

Step 2: Count bad paths (those going below the $x$-axis). Consider a bad path that first touches $y = -1$ at some point. Let this occur after the $k$-th step, and reflect the portion of the path after this point across the line $y = -1$.

After reflection:

• Up steps become down steps and vice versa
• The endpoint changes from $(2n, 0)$ to $(2n, -2)$

This gives a bijection between bad paths from $(0,0)$ to $(2n,0)$ and all paths from $(0,0)$ to $(2n,-2)$.

Step 3: Count paths to $(2n,-2)$. A path from $(0,0)$ to $(2n,-2)$ takes $2n$ steps with net vertical displacement $-2$. This requires $(n-1)$ up steps and $(n+1)$ down steps, giving $\binom{2n}{n+1}$ paths.

Step 4: Apply inclusion-exclusion. $C_n = \text{(good paths)} = \text{(all paths)} - \text{(bad paths)}$ $= \binom{2n}{n} - \binom{2n}{n+1}$

Using the identity $\binom{2n}{n+1} = \frac{n}{n+1}\binom{2n}{n}$: $C_n = \binom{2n}{n} - \frac{n}{n+1}\binom{2n}{n} = \binom{2n}{n}\left(1 - \frac{n}{n+1}\right) = \frac{1}{n+1}\binom{2n}{n}$

The Catalan numbers satisfy the recurrence $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ with $C_0 = 1$.

Let $C(x) = \sum_{n=0}^\infty C_n x^n$ be the generating function. The recurrence translates to: $C(x) = 1 + xC(x)^2$

This is a quadratic equation in $C(x)$: $xC(x)^2 - C(x) + 1 = 0$

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

Since $C(0) = C_0 = 1$ (requiring the series to have constant term 1), we choose the minus sign: $C(x) = \frac{1 - \sqrt{1-4x}}{2x}$

Expanding $\sqrt{1-4x}$ using the generalized binomial theorem with $\alpha = 1/2$: $\sqrt{1-4x} = \sum_{n=0}^\infty \binom{1/2}{n}(-4x)^n$

where $\binom{1/2}{n} = \frac{(1/2)(1/2-1)\cdots(1/2-n+1)}{n!} = \frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}$ for $n \geq 1$.

After algebraic manipulation: $C(x) = \sum_{n=0}^\infty \frac{1}{n+1}\binom{2n}{n}x^n$

Comparing coefficients gives $C_n = \frac{1}{n+1}\binom{2n}{n}$.