Recurrence Relations — Setting Them Up, Solving Linear Recurrences, and the Master Theorem for Algorithms

A recurrence relation defines each term of a sequence using earlier terms: aₙ = aₙ₋₁ + aₙ₋₂. Recurrences are how we count recursive structures and how we analyse recursive algorithms — merge sort, binary search, divide and conquer. This is where discrete maths meets DSA directly.

1. Modelling with recurrences

Tower of Hanoi. Move n disks: move n−1 to the spare peg, move the biggest, move n−1 back on top. So Hₙ = 2Hₙ₋₁ + 1, H₁ = 1.

Tiling a 2×n board with 2×1 dominoes. The first column is either one vertical domino (leaving 2×(n−1)) or two horizontal dominoes (leaving 2×(n−2)). So Tₙ = Tₙ₋₁ + Tₙ₋₂ — Fibonacci again.

Binary strings of length n with no two consecutive 1s. Ends in 0 → any valid string of length n−1 plus 0; ends in 1 → must be "…01" → valid string of length n−2 plus 01. So Bₙ = Bₙ₋₁ + Bₙ₋₂, B₁ = 2, B₂ = 3.

Check the binary-strings recurrence against brute force:

from itertools import product

def brute(n):
    return sum(1 for s in product("01", repeat=n) if "11" not in "".join(s))

def recur(n):
    a, b = 2, 3                 # B1, B2
    if n == 1: return a
    for _ in range(n - 2):
        a, b = b, a + b
    return b

print([brute(n) for n in range(1, 11)])
print([recur(n) for n in range(1, 11)])

[2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

2. Solving linear homogeneous recurrences

Form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ (constant coefficients, no extra term).

1. Write the characteristic equation: r² = c₁r + c₂.
2. Find roots r₁, r₂.
3. Distinct roots: aₙ = A·r₁ⁿ + B·r₂ⁿ. Repeated root r: aₙ = (A + Bn)·rⁿ.
4. Use the initial conditions to find A and B.

Example: aₙ = 5aₙ₋₁ − 6aₙ₋₂, a₀ = 1, a₁ = 4. r² − 5r + 6 = 0 → r = 2, 3. So aₙ = A·2ⁿ + B·3ⁿ. a₀: A + B = 1; a₁: 2A + 3B = 4 → B = 2, A = −1. So aₙ = −2ⁿ + 2·3ⁿ. Check both ways:

def by_recurrence(n):
    a = [1, 4]
    for i in range(2, n + 1):
        a.append(5 * a[i - 1] - 6 * a[i - 2])
    return a[n]

closed = lambda n: -(2 ** n) + 2 * 3 ** n
print([by_recurrence(n) for n in range(8)])
print([closed(n) for n in range(8)])

[1, 4, 14, 46, 146, 454, 1394, 4246]
[1, 4, 14, 46, 146, 454, 1394, 4246]

Fibonacci (Fₙ = Fₙ₋₁ + Fₙ₋₂) has roots (1 ± √5)/2, giving Binet's formula Fₙ = (φⁿ − ψⁿ)/√5 with φ ≈ 1.618 — so Fibonacci numbers grow exponentially, ~1.618ⁿ, which is why naive recursive Fibonacci is so slow.

3. Non-homogeneous recurrences

aₙ = c·aₙ₋₁ + f(n): solution = (homogeneous solution) + (a particular solution).

Tower of Hanoi: Hₙ = 2Hₙ₋₁ + 1. Homogeneous part: A·2ⁿ. Try a constant particular solution p: p = 2p + 1 → p = −1. So Hₙ = A·2ⁿ − 1; H₁ = 1 gives A = 1. Hₙ = 2ⁿ − 1.

def hanoi_moves(n, src="A", dst="C", via="B", moves=None):
    if moves is None: moves = []
    if n == 0: return moves
    hanoi_moves(n - 1, src, via, dst, moves)
    moves.append((src, dst))
    hanoi_moves(n - 1, via, dst, src, moves)
    return moves

for n in range(1, 8):
    print(n, len(hanoi_moves(n)), 2 ** n - 1)
print("first moves for 3 disks:", hanoi_moves(3))

1 1 1
2 3 3
3 7 7
4 15 15
5 31 31
6 63 63
7 127 127
first moves for 3 disks: [('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]

64 disks would need 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹ moves — the legend's priests are safe for a very long time.

4. Recurrences for algorithms

Divide-and-conquer algorithms give recurrences of the form T(n) = a·T(n/b) + f(n): a subproblems, each of size n/b, plus f(n) work to split/combine.

5. The Master Theorem

For T(n) = a·T(n/b) + Θ(nᵈ) with a ≥ 1, b > 1, compare d with log_b a:

import math

def master(a, b, d):
    crit = math.log(a, b)
    if abs(d - crit) < 1e-9:
        return f"Theta(n^{d} log n)"
    if d < crit:
        return f"Theta(n^{crit:.3f})"
    return f"Theta(n^{d})"

for name, a, b, d in [("binary search", 1, 2, 0), ("merge sort", 2, 2, 1),
                      ("Karatsuba", 3, 2, 1), ("T(n)=8T(n/2)+n^2", 8, 2, 2), ("T(n)=2T(n/2)+n^2", 2, 2, 2)]:
    print(f"{name:18} -> {master(a, b, d)}")

binary search      -> Theta(n^0 log n)
merge sort         -> Theta(n^1 log n)
Karatsuba          -> Theta(n^1.585)
T(n)=8T(n/2)+n^2   -> Theta(n^3.000)
T(n)=2T(n/2)+n^2   -> Theta(n^2)

(Binary search's "n^0 log n" is just Θ(log n).) The Master Theorem doesn't cover everything — e.g. T(n) = T(n−1) + n (use the substitution/unrolling method: Θ(n²)).

Common mistakes

• Forgetting initial conditions (a recurrence alone doesn't define a sequence).
• Using A·rⁿ + B·rⁿ for a repeated root (it must be (A + Bn)rⁿ).
• Applying the Master Theorem to T(n) = T(n − 1) + … (not of the form T(n/b)).
• Mixing up a and b (a = number of subproblems, b = shrink factor).

Quick recap

• Model by thinking about the first/last step (Hanoi, tiling, strings).
• Linear homogeneous: characteristic equation; distinct roots A·r₁ⁿ + B·r₂ⁿ, repeated (A + Bn)rⁿ.
• Non-homogeneous: homogeneous + particular solution (Hanoi = 2ⁿ − 1).
• Master Theorem: compare d with log_b a → Θ(n^(log_b a)), Θ(nᵈ log n) or Θ(nᵈ).