A Recurrence Relation for the Catalan Numbers

On The Catalan Numbers page we defined the Catalan Numbers $C_n$ for each $n \in \{0, 1, 2, ... \}$ to be:

(1)

\begin{align} \quad C_n = \frac{1}{1 + n} \binom{2n}{n} \end{align}

We proved that the Catalan Numbers arise to be the number of sequences $(a_i)_{i=1}^{2n}$ of $n$ many $+1$s and $n$ many $-1$s such that each partial sum $s_k = a_1 + a_2 + ... + a_k > 0$ for $k \in \{1, 2, ..., 2n \}$.

We will now come up with a recurrence relation for the Catalan numbers.

Theorem 1: For each $n \in \{1, 2, ... \}$, $C_n = \frac{4n - 2}{n + 1} C_{n-1}$.

• Proof: Let $n \in \{1, 2, ... \}$. Then $C_n = \frac{1}{1 + n} \binom{2n}{n} = \frac{1}{1 + n} \cdot \frac{(2n)!}{n! \cdot n!}$ and:

(2)

\begin{align} \quad C_{n-1} = \frac{1}{1 + (n - 1)} \binom{2(n-1)}{n-1} \\ \quad C_{n-1} = \frac{1}{n} \binom{2n - 2}{n - 1} \\ \quad C_{n-1} = \frac{1}{n} \cdot \frac{(2n - 2)!}{(n - 1)! \cdot (2n - 2 - (n - 1))!} \\ \quad C_{n-1} = \frac{1}{n} \cdot \frac{(2n - 2)!}{(n - 1)! \cdot (n - 1)!} \end{align}

• Therefore:

(3)

\begin{align} \quad \frac{C_n}{C_{n-1}} = \frac{1}{1 + n} \cdot \frac{(2n)!}{n! \cdot n!} \cdot n \cdot \frac{(n - 1)! \cdot (n - 1)!}{(2n - 2)!} \\ \quad \frac{C_n}{C_{n-1}} = \frac{n}{1 + n}\cdot \frac{2n \cdot (2n - 1)}{n \cdot n} \\ \quad \frac{C_n}{C_{n-1}} = \frac{n}{1 + n} \cdot \frac{4n^2 - 2n}{n^2} \\ \quad \frac{C_n}{C_{n-1}} = \frac{4n^3 - 2n^2}{n^2 + n^3} \\ \quad \frac{C_n}{C_{n-1}} = \frac{4n - 2}{n + 1} \\ \quad C_n = \frac{4n - 2}{n + 1} C_{n-1} \quad \blacksquare \end{align}

For example, if we are given that $C_4 = 14$, then to find $C_5$ we just apply the formula given in Theorem 1:

(4)

\begin{align} \quad C_5 = \frac{4(5) - 2}{(5) + 1} \cdot (14) \\ \quad C_5 = \frac{18}{6} \cdot 14 \\ \quad C_5 = 42 \end{align}