Recurrence Relations and Catalan Numbers

Recurrence relations provide a powerful method for counting by expressing the solution for size $n$ in terms of solutions for smaller sizes. The Catalan numbers represent one of the most ubiquitous sequences in combinatorics, appearing in diverse counting problems.

DefinitionRecurrence Relation

A recurrence relation is an equation that defines a sequence $\{a_n\}$ in terms of previous terms. A linear recurrence relation with constant coefficients has the form: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n)$ where $c_i$ are constants and $f(n)$ is a function of $n$ . If $f(n) = 0$ , the recurrence is homogeneous.

The characteristic equation method solves homogeneous linear recurrences. For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ , we solve: $x^2 = c_1 x + c_2$ If roots are $r_1, r_2$ , the general solution is $a_n = A r_1^n + B r_2^n$ (or $a_n = (A + Bn)r^n$ for repeated root $r$ ).

ExampleFibonacci Numbers

The Fibonacci sequence $F_n$ satisfies $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0, F_1 = 1$ . The characteristic equation is: $x^2 = x + 1 \implies x^2 - x - 1 = 0$

The roots are $\phi = \frac{1 + \sqrt{5}}{2}$ (golden ratio) and $\hat{\phi} = \frac{1 - \sqrt{5}}{2}$ . Thus: $F_n = \frac{1}{\sqrt{5}}\left(\phi^n - \hat{\phi}^n\right) = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

This closed form is known as Binet's formula.

DefinitionCatalan Numbers

The Catalan numbers $C_n$ count numerous combinatorial structures. They can be defined by:

Explicit formula: $C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$
Recurrence relation: $C_0 = 1$ and $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ for $n \geq 1$
Alternative recurrence: $C_n = \frac{2(2n-1)}{n+1}C_{n-1}$

The first few values are: $1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

The recurrence $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ arises naturally when counting binary trees: a tree with $n$ internal nodes can have a left subtree with $i$ nodes and a right subtree with $n-1-i$ nodes.

ExampleApplications of Catalan Numbers

The $n$ -th Catalan number $C_n$ counts:

Balanced parentheses: ways to arrange $n$ pairs of parentheses correctly
Binary trees: full binary trees with $n+1$ leaves
Dyck paths: lattice paths from $(0,0)$ to $(2n,0)$ using steps $(1,1)$ and $(1,-1)$ that never go below the $x$ -axis
Triangulations: ways to divide a convex $(n+2)$ -gon into triangles
Stack sequences: sequences of $n$ pushes and $n$ pops that are valid
Non-crossing partitions: ways to partition $[n]$ without crossing arcs when drawn on a circle

For example, $C_3 = 5$ corresponds to: ((())), (()()), (())(), ()(()), ()()()

Remark

The Catalan numbers grow as $C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$ by Stirling's approximation. This asymptotic behavior is characteristic of sequences satisfying quadratic recurrences with a unique dominant solution.

DefinitionGenerating Function for Catalan Numbers

The ordinary generating function for Catalan numbers is: $C(x) = \sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1-4x}}{2x}$

This function satisfies the functional equation $C(x) = 1 + xC(x)^2$ , which directly encodes the recurrence relation. Solving this quadratic equation yields the explicit formula above.

The study of recurrence relations connects to linear algebra (matrix methods), complex analysis (generating functions), and differential equations (continuous analogs), making it a central tool in enumerative combinatorics.