Recurrence Relations

Sometimes the easiest way to count something of size n is to relate it to the same thing of size n-1. A recurrence relation defines a sequence by expressing each term in terms of earlier ones, together with a few starting values. It is the combinatorial version of dominoes: knock down the base cases and the rule topples the rest, forever. This page is about writing such rules — and, crucially, solving them for a closed formula.

The most famous example is the Fibonacci sequence, where each term is the sum of the two before it:

F_n = F_{n-1} + F_{n-2}, \qquad F_0 = 0,\quad F_1 = 1,

giving 0, 1, 1, 2, 3, 5, 8, 13, 21, \dots. It counts real things: the number of ways to tile a 1 \times n strip with 1\times1 squares and 1\times2 dominoes is exactly F_{n+1} — condition on the last tile (a square leaves a strip of length n-1, a domino leaves n-2), and the two cases add, which is the recurrence.

Setting up recurrences by conditioning

The art is the same every time: take a structure of size n, look at one "last decision", and count how each choice reduces to smaller versions of the same problem. Two classics:

Subsets with no two adjacent elements

Let a_n be the number of subsets of \{1, \dots, n\} containing no two consecutive integers. Condition on element n: if it is out, the rest is any valid subset of \{1,\dots,n-1\} (a_{n-1} of them); if it is in, then n-1 must be out and the rest is a valid subset of \{1,\dots,n-2\} (a_{n-2}). So a_n = a_{n-1} + a_{n-2} — Fibonacci again, in disguise.

The Towers of Hanoi

To move n disks between pegs you must move the top n-1 off, move the big disk, then move the n-1 back: T_n = 2T_{n-1} + 1, with T_1 = 1. Unrolling gives T_n = 2^n - 1 — the source of the legend that finishing a 64-disk tower would take longer than the age of the universe (2^{64} - 1 moves).

Play with a linear recurrence

A linear recurrence with constant coefficients has the form x_n = c_1 x_{n-1} + c_2 x_{n-2}. Set both coefficients to 1 and you have Fibonacci; nudge them and the whole growth pattern changes — gently rising, exploding, or oscillating. The dots are the terms (rescaled to fit); watch how sensitive the long-run behaviour is to the coefficients.

Solving linear recurrences: the characteristic equation

A recurrence defines a sequence, but computing F_{100} by iterating is slow — we want a closed form. The trick is to guess that a solution grows like a geometric sequence, x_n = r^n, and see which r work. Substituting into x_n = c_1 x_{n-1} + c_2 x_{n-2} and dividing by r^{n-2} gives the characteristic equation:

r^2 = c_1 r + c_2 \quad\Longleftrightarrow\quad r^2 - c_1 r - c_2 = 0.

For x_n = c_1 x_{n-1} + c_2 x_{n-2} with characteristic roots r_1, r_2:

Fibonacci in closed form — Binet's formula

For Fibonacci, c_1 = c_2 = 1, so r^2 - r - 1 = 0, whose roots are the golden ratio \varphi = \frac{1+\sqrt5}{2} and its conjugate \psi = \frac{1-\sqrt5}{2}. Fitting F_0 = 0, F_1 = 1 gives

F_n = \frac{\varphi^{\,n} - \psi^{\,n}}{\sqrt5}.

An expression built from irrational \sqrt5's that spits out a whole number every single time. Because |\psi| < 1, the second term vanishes and F_n is simply the nearest integer to \varphi^n / \sqrt5 — which is why Fibonacci numbers grow geometrically, each roughly \varphi \approx 1.618 times the last.

A recurrence like T_n = 2T_{n-1} + 1 is inhomogeneous — the extra +1 is a forcing term. Solve it the way you solve a driven differential equation: find the homogeneous solution (A\cdot2^n here) and add any particular solution (a constant P with P = 2P + 1, so P = -1), giving T_n = A\cdot 2^n - 1; the initial condition sets A = 1 and recovers T_n = 2^n - 1. The parallel with linear ODEs is not a coincidence — both are linear operators, one on sequences and one on functions.