Recursion, Catalan Numbers & Generating Functions

A recurrence counts a large problem in terms of smaller versions of itself. To build one:

• [leftmargin=*,itemsep=1pt]
• Define the sequence precisely. Let $a_n$ be the number of ways to do the task of “size” $n$. Being sloppy here is the #1 source of errors --- write a one-sentence definition.
• Condition on a first (or last) choice. Look at the object and split into cases based on one feature: the first tile, the last step, whether an element is used, the height of the last column, etc.
• Express each case using smaller $a_k$. Each case should leave a strictly smaller sub-problem of the same type, so it is counted by $a_{k}$ for some $k<n$.
• Nail the base cases. Determine $a_0$ (or $a_1$) directly by hand. Count the “empty” object carefully: usually $a_0=1$.

The recurrence plus base cases determines every term.

The Fibonacci numbers satisfy

giving $1,1,2,3,5,8,13,21,34,55,\dots$ Many tiling problems reduce to this.

Square--domino tilings. Let $t_n$ be the number of ways to tile a $1\times n$ strip using $1\times1$ squares and $1\times2$ dominoes. Look at the tile covering the last cell: a square (leaving a $1\times(n-1)$ strip) or a domino (leaving a $1\times(n-2)$ strip). So $t_n=t_{n-1}+t_{n-2}$ with $t_0=1,\ t_1=1$, i.e. $t_n=f_{n+1}$.

When the next choice depends on the current situation, define one sequence per state and let them recurse together. Steps:

• [leftmargin=*,itemsep=1pt]
• Identify the finite information (the “state”) you must remember to extend a valid object by one step.
• Define $a_n,b_n,\dots$ = number of length-$n$ objects ending in each state.
• Write transition equations: each state's next value is a sum over states that may legally precede it.
• The answer is usually the sum of all states at length $n$.

This is the “transfer matrix” / finite-automaton viewpoint.

The Catalan numbers are

First values:

They count an astonishing number of things. Three canonical interpretations:

• [leftmargin=*,itemsep=1pt]
• Lattice paths / ballots: monotonic paths from $(0,0)$ to $(n,n)$ using steps right/up that never cross above the diagonal $y=x$. Equivalently, sequences of $n$ $+1$s and $n$ $-1$s with every partial sum $\ge 0$.
• Balanced parentheses: the number of ways to correctly match $n$ pairs of parentheses (every prefix has $\#($ $\ge$ $\#)$).
• Triangulations: the number of ways to cut a convex $(n+2)$-gon into triangles using non-crossing diagonals.

Other appearances: binary trees with $n$ internal nodes, non-crossing handshakes among $2n$ people, mountain ranges, and stack-sortable permutations.

A (ordinary) generating function packages a sequence $a_0,a_1,a_2,\dots$ into one formal power series

The exponent of $x$ is a “label” tracking a total (size, weight, sum), and the coefficient counts objects with that total. The magic:

If $A(x)$ counts choices for part 1 (weighted by size) and $B(x)$ counts part 2, then the product $A(x)B(x)$ has $x^n$-coefficient $\sum_k a_k b_{n-k}$ --- exactly the number of ways to split total $n$ between the two parts. Useful building blocks:

For a linear recurrence with constant coefficients

guess $a_n=r^n$. Substituting and dividing by $r^{n-2}$ gives the characteristic equation

• [leftmargin=*,itemsep=1pt]
• Distinct roots $r_1\ne r_2$: the general solution is $a_n=\alpha\, r_1^{\,n}+\beta\, r_2^{\,n}$.
• Repeated root $r$: use $a_n=(\alpha+\beta n)\,r^{\,n}$.

Fix $\alpha,\beta$ from two initial values. The same idea extends to order $k$: a degree-$k$ characteristic polynomial with $k$ roots.

(A) The Catalan closed form by reflection. Count lattice paths from $(0,0)$ to $(n,n)$ (steps R and U) that stay weakly below the diagonal. Total paths: $\binom{2n}{n}$. A bad path touches the line $y=x+1$. Reflect the portion of a bad path after its first touch across $y=x+1$: this bijects bad paths with all paths from $(0,0)$ to $(n-1,n+1)$, of which there are $\binom{2n}{n+1}$. Hence

(B) Solving a recurrence with a generating function. Let $C(x)=\sum_{n\ge0}C_nx^n$. The convolution $C_{n+1}=\sum_i C_iC_{n-i}$ says $C(x)=1+xC(x)^2$. Solving the quadratic,

and expanding $\sqrt{1-4x}$ by the binomial series recovers $C_n=\frac1{n+1}\binom{2n}{n}$. This “turn the recurrence into an equation for $A(x)$, solve, expand” pipeline is the general method.

(C) Binet's formula for Fibonacci. The characteristic equation $r^2=r+1$ has roots $\varphi=\frac{1+\sqrt5}{2}$ and $\psi=\frac{1-\sqrt5}{2}$. Then

Since $|\psi|<1$, $f_n$ is the nearest integer to $\varphi^{\,n}/\sqrt5$, so Fibonacci numbers grow like $\varphi^{\,n}$.

A linear recurrence with a forcing term,

is solved by

where $a_n^{(h)}$ is the general solution of the homogeneous part (characteristic roots, as before) and $a_n^{(p)}$ is any one particular solution. To find $a_n^{(p)}$, guess a form matching $g(n)$ and solve for its constants:

Resonance (the crucial trap). If your guess already solves the homogeneous equation --- e.g. $g(n)=b^{\,n}$ but $b$ is a characteristic root, or $g(n)$ is constant but $r=1$ is a root --- multiply the guess by $n$ (by $n^m$ if $b$ is a root of multiplicity $m$). This is the same “multiply by $n$ for a repeated root” rule seen in the homogeneous case.

A coupled linear recurrence among finitely many states is one matrix $T$ acting on a state vector. If $\mathbf{v}_n$ collects the state values at step $n$ and $\mathbf{v}_n=T\mathbf{v}_{n-1}$, then

For the Fibonacci recurrence, taking $\mathbf{v}_n=\begin{bmatrix}f_{n+1}\\ f_n\end{bmatrix}$,

The matrix's eigenvalues are exactly the characteristic roots $\varphi,\psi$, which is why $T^{\,n}$ (hence every entry) is a combination of $\varphi^{\,n}$ and $\psi^{\,n}$ --- another route to Binet's formula. Taking determinants of the boxed identity gives $f_{n+1}f_{n-1}-f_n^2=(-1)^n$ instantly (Cassini's identity).

Counting walks. If $M$ is the adjacency matrix of a (multi)graph, then $(M^{\,n})_{ij}$ counts walks of length $n$ from vertex $i$ to $j$, and $\operatorname{tr}(M^{\,n})=\sum_k\lambda_k^{\,n}$ counts closed walks. This packages “count paths through states” as matrix powers.

The reflection principle is one proof of the Catalan/ballot counts; the cycle lemma is a slicker, purely combinatorial one.

Cycle Lemma (Dvoretzky--Motzkin). Take any sequence of $n$ steps that are $+1$'s and $-1$'s summing to $+1$ (so $\frac{n+1}{2}$ ups and $\frac{n-1}{2}$ downs). Among its $n$ cyclic rotations, exactly one has all partial sums strictly positive.

Ballot Theorem. In an election where $A$ gets $a$ votes and $B$ gets $b<a$ votes, the number of orderings of the ballots in which $A$ is strictly ahead throughout is

Catalan is the boundary case: paths from $(0,0)$ to $(n,n)$ staying strictly below the diagonal except at the ends correspond to $a=n+1,\ b=n$ shifted, and the ballot formula collapses to $C_n=\frac{1}{n+1}\binom{2n}{n}$.

When objects are built on labeled elements (people, positions $1..n$ that are distinguishable), the right bookkeeping tool is the exponential generating function

The key rule mirrors the ordinary case but with a binomial-flavored product:

The $\binom{n}{k}$ appears because you first choose which labels go to the $A$-part. Building blocks:

The Exponential Formula $\widehat{A}(x)=e^{\widehat{C}(x)}$ passes from “connected” pieces $\widehat{C}$ to arbitrary disjoint unions of them (set partitions into blocks, permutations into cycles, graphs into components).