Recurrence relations

A recurrence relation defines each term of a sequence from earlier terms, plus initial conditions to start it:

• Fibonacci: F(n) = F(n − 1) + F(n − 2), with F(0) = 0 and F(1) = 1.
• Savings with 7% interest: S(n) = 1.07 × S(n − 1), with S(0) = 1000.

Recurrences describe recursive algorithms exactly, so solving one tells you how fast the algorithm is.

The Tower of Hanoi

Move n disks from peg A to peg C, one disk at a time, never putting a bigger disk on a smaller one. To move n disks: move the top n − 1 to B, move the biggest to C, move the n − 1 from B to C. So the number of moves H(n) satisfies

H(n) = 2 H(n − 1) + 1,   H(1) = 1

moves = []

def hanoi(n, source, spare, target):
    if n == 0:
        return
    hanoi(n - 1, source, target, spare)     # clear the way
    moves.append(f"{n}:{source}→{target}")   # move the biggest disk
    hanoi(n - 1, spare, source, target)     # put the rest back on it

hanoi(3, "A", "B", "C")
print(len(moves), "moves:", " ".join(moves))
print("2**3 - 1 =", 2 ** 3 - 1)

Solving by unrolling

Substitute the recurrence into itself until a pattern appears:

H(n) = 2 H(n − 1) + 1
     = 2 (2 H(n − 2) + 1) + 1        = 4 H(n − 2) + 2 + 1
     = 8 H(n − 3) + 4 + 2 + 1
     = 2ⁿ⁻¹ H(1) + 2ⁿ⁻² + ... + 2 + 1
     = 2ⁿ − 1

Then prove the guess by induction. 64 disks need 2⁶⁴ − 1 moves: at one move a second, about 585 billion years.

Linear homogeneous recurrences

For a recurrence a(n) = c₁ a(n − 1) + c₂ a(n − 2), try a(n) = rⁿ. Dividing by rⁿ⁻² gives the characteristic equation

r² = c₁ r + c₂

If it has two different roots r₁ and r₂, every solution is a(n) = α r₁ⁿ + β r₂ⁿ, and the initial conditions fix α and β.

Example. a(n) = 5 a(n − 1) − 6 a(n − 2), a(0) = 1, a(1) = 4. The equation r² = 5r − 6 has roots 2 and 3, so a(n) = α 2ⁿ + β 3ⁿ. From a(0): α + β = 1; from a(1): 2α + 3β = 4. So β = 2, α = −1, and a(n) = 2 × 3ⁿ − 2ⁿ.

Fibonacci works the same way: r² = r + 1 has roots (1 ± √5)/2, which gives Binet's formula with the golden ratio φ ≈ 1.618. So F(n) grows like φⁿ: exponentially.

# a(n) = 5 a(n-1) - 6 a(n-2), a(0) = 1, a(1) = 4.  Solved: a(n) = 2 * 3**n - 2**n
a = [1, 4]
for n in range(2, 8):
    a.append(5 * a[n - 1] - 6 * a[n - 2])

closed = [2 * 3 ** n - 2 ** n for n in range(8)]
print("by the recurrence:", a)
print("by the formula:   ", closed)
print("the same:", a == closed)

Divide and conquer

Merge sort splits the list in half, sorts both halves and merges them in n steps:

T(n) = 2 T(n/2) + n

Unrolling gives n at each of log₂ n levels: T(n) = n log₂ n. Binary search, T(n) = T(n/2) + 1, gives log₂ n. The Master Theorem, in the Algorithms course, solves this whole family at once.

Mark lesson complete