Many quantities are easier to describe in terms of previous values than with a direct formula: the number of moves needed to solve a puzzle, the running time of a recursive algorithm, the balance of an account earning interest. A recurrence relation expresses exactly this link. Solving it means finding a closed form, a formula that gives the n-th value directly without computing all the ones before it.
Definition
A recurrence relation for a sequence a₀, a₁, a₂, … is an equation that expresses aₙ in terms of some earlier terms, together with one or more initial conditions.
Examples:
- aₙ = aₙ₋₁ + 3, with a₀ = 2: the arithmetic sequence 2, 5, 8, 11, …
- aₙ = 2aₙ₋₁, with a₀ = 1: powers of 2.
- Fₙ = Fₙ₋₁ + Fₙ₋₂, with F₀ = 0 and F₁ = 1: the Fibonacci numbers.
Without initial conditions a recurrence does not determine a unique sequence: aₙ = 2aₙ₋₁ is satisfied both by 1, 2, 4, … and by 3, 6, 12, …
Method 1: iterated substitution
Substitute the recurrence into itself until a pattern emerges, then verify it by induction.
The Tower of Hanoi
To move n discs from the first peg to the third, you must move the top n − 1 to the spare peg, move the largest disc, and then bring the n − 1 back on top of it. The minimum number of moves satisfies:
Hₙ = 2Hₙ₋₁ + 1, with H₁ = 1
Substituting:
Hₙ = 2(2Hₙ₋₂ + 1) + 1 = 4Hₙ₋₂ + 2 + 1 = 8Hₙ₋₃ + 4 + 2 + 1 = …
After n − 1 steps: Hₙ = 2ⁿ⁻¹H₁ + 2ⁿ⁻² + … + 2 + 1 = 2ⁿ⁻¹ + … + 1 = 2ⁿ − 1.
With 10 discs you need 1023 moves; with 64 discs, the number is about 1.8 · 10¹⁹. The closed form makes obvious a growth that the recurrence hides.
Method 2: the characteristic equation
For second-order linear homogeneous recurrences with constant coefficients, of the form
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂
look for a solution of the form aₙ = rⁿ. Substituting and dividing by rⁿ⁻² gives the characteristic equation:
r² − c₁r − c₂ = 0
- If it has two distinct roots r₁ and r₂, the general solution is aₙ = α r₁ⁿ + β r₂ⁿ.
- If it has a double root r, the general solution is aₙ = (α + βn) rⁿ.
The constants α and β come from the initial conditions.
Worked example
aₙ = 5aₙ₋₁ − 6aₙ₋₂, with a₀ = 1 and a₁ = 4.
Characteristic equation: r² − 5r + 6 = 0, roots 2 and 3. So aₙ = α · 2ⁿ + β · 3ⁿ.
- n = 0: α + β = 1
- n = 1: 2α + 3β = 4
Solving: β = 2, α = −1. Closed form: aₙ = 2 · 3ⁿ − 2ⁿ. Check: a₂ = 18 − 4 = 14, and from the recurrence 5 · 4 − 6 · 1 = 14.
Fibonacci
For Fₙ = Fₙ₋₁ + Fₙ₋₂ the equation is r² − r − 1 = 0, with roots φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 − √5)/2 ≈ −0.618. Imposing F₀ = 0 and F₁ = 1 gives Binet's formula:
Fₙ = (φⁿ − ψⁿ) / √5
Since |ψ| < 1, the term ψⁿ becomes negligible and Fₙ is the integer nearest to φⁿ/√5. Fibonacci numbers therefore grow exponentially, with base about 1.618.
Recurrences and algorithms
The running time of a recursive algorithm naturally satisfies a recurrence. Two instructive examples.
Naive recursive Fibonacci
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
The number of calls T(n) satisfies T(n) = T(n − 1) + T(n − 2) + 1, which grows like Fₙ, that is, exponentially. By storing results already computed, or iterating from the bottom up, the cost becomes linear.
Divide and conquer
An algorithm that splits the problem into two halves, solves them recursively and combines the results in linear time satisfies T(n) = 2T(n/2) + cn. Iterating, the total work at each level of recursion is cn, and there are about log₂ n levels. The total is of order n log n: this is the case of merge sort. This general pattern is captured by the so-called master theorem, which gives the solution for recurrences of the form T(n) = aT(n/b) + f(n).
A practical check
When you find a closed form, it is always worth checking it numerically on the first few values:
def recurrence(n):
a = [1, 4]
for k in range(2, n + 1):
a.append(5 * a[-1] - 6 * a[-2])
return a[n]
assert all(recurrence(n) == 2 * 3**n - 2**n for n in range(20))
The check does not replace a proof, but it immediately catches arithmetic errors in the constants.
In short
- A recurrence defines each term through earlier ones and needs initial conditions.
- Iterated substitution reveals the pattern, which is then confirmed by induction.
- Linear homogeneous recurrences are solved with the characteristic equation.
- Fibonacci grows like φⁿ; the Tower of Hanoi needs 2ⁿ − 1 moves.
- The cost of recursive algorithms is a recurrence: divide and conquer often leads to n log n.
