Recurrence Relations

Defining Things in Terms of Themselves

A recurrence relation defines each term of a sequence using earlier terms, plus one or more initial conditions to start. The most famous is the Fibonacci sequence: $F(n) = F(n-1) + F(n-2)$ with $F(0) = 0, F(1) = 1$, giving $0, 1, 1, 2, 3, 5, 8, 13, \dots$. Recurrences are how we describe processes that build on their own previous state — and they are the mathematical shadow of recursion in programming.

To evaluate a recurrence you unfold it from the initial conditions forward. To understand it you often want a closed form — a direct formula for $F(n)$ that avoids computing all earlier terms. For example, the recurrence $a(n) = 2\,a(n-1)$ with $a(0) = 1$ has the closed form $a(n) = 2^n$. Finding closed forms uses techniques like the characteristic equation for linear recurrences.

Recurrences are central to algorithm analysis. A divide-and-conquer algorithm that splits a problem of size $n$ into two halves and does linear work has running time $T(n) = 2\,T(n/2) + n$ — a recurrence whose solution ($n \log n$) is the algorithm's complexity. The Master Theorem solves this whole family of divide-and-conquer recurrences at a glance, which is why recurrences and complexity are studied together.

Two essentials make a recurrence well-defined: the recursive rule (how a term depends on earlier ones) and the initial conditions (the starting values). Omit the initial conditions and the sequence is undetermined — exactly like a recursive function with no base case, which never terminates.

Common pitfall: forgetting the initial conditions, or misreading which earlier terms a recurrence depends on. Without initial values a recurrence defines no specific sequence — just as a recursive function without a base case recurses forever. And $F(n) = F(n-1) + F(n-2)$ needs two starting values (not one), because each term reaches back two steps; supplying too few initial conditions leaves the sequence undefined.

The Fibonacci sequence as a row of values; each new term is drawn as the accent sum of the two preceding boxes, unfolding 0, 1, 1, 2, 3, 5, 8.

$$F(n) = F(n-1) + F(n-2)$$