8.1 What is a Recurrence Relation?

A recurrence relation defines a sequence by expressing a(n) in terms of earlier terms, plus enough initial conditions to pin the sequence down. Recurrences are the native language of recursive algorithms: binary search satisfies T(n) = T(n/2) + 1, merge sort T(n) = 2T(n/2) + cn.

Formulating one: Let a(n) = number of binary strings of length n with no two consecutive 0s. Classify by the first symbol: strings starting with 1 (a(n−1) of them) or with 01 (a(n−2)). So a(n) = a(n−1) + a(n−2), a(1) = 2, a(2) = 3 — a Fibonacci-type recurrence appearing straight out of a counting problem.

8.2 Worked Example 1 — Tower of Hanoi by Iteration

Moving n disks needs: move n − 1 disks aside (H(n−1)), move the largest disk (1), move n − 1 disks back on top (H(n−1)):

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

Unfold (back-substitution):

1. H(n) = 2H(n−1) + 1 = 2(2H(n−2) + 1) + 1 = 2^2·H(n−2) + 2 + 1
2. After k unfoldings: H(n) = 2^k·H(n−k) + (2^(k−1) + ... + 2 + 1)
3. Set k = n − 1: H(n) = 2^(n−1)·1 + (2^(n−1) − 1) = 2^n − 1.

Verify: H(3) = 7 ✔ (7 moves for 3 disks). With 64 disks, 2^64 − 1 ≈ 1.8 × 10^19 moves — exponential recurrences explain why some algorithms cannot scale.

8.3 Linear Homogeneous Recurrences with Constant Coefficients

For a(n) = c1·a(n−1) + c2·a(n−2), substitute a(n) = r^n to get the characteristic equation r^2 − c1·r − c2 = 0.

A and B come from the initial conditions.

Worked Example 2 — distinct roots. Solve a(n) = a(n−1) + 2a(n−2), a(0) = 2, a(1) = 7.

1. Characteristic equation: r^2 − r − 2 = 0 → (r − 2)(r + 1) = 0 → r = 2, −1.
2. General solution: a(n) = A·2^n + B·(−1)^n.
3. n = 0: A + B = 2; n = 1: 2A − B = 7. Adding: 3A = 9 → A = 3, B = −1.
4. a(n) = 3·2^n − (−1)^n. Verify: a(2) should be a(1) + 2a(0) = 7 + 4 = 11; formula gives 12 − 1 = 11. ✔

Repeated-root case: a(n) = 4a(n−1) − 4a(n−2), a(0) = 1, a(1) = 6 has r^2 − 4r + 4 = (r − 2)^2, so a(n) = (A + Bn)2^n; conditions give A = 1, B = 2, i.e., a(n) = (1 + 2n)2^n. Check: a(2) = 4·6 − 4·1 = 20 = (1 + 4)·4. ✔

8.4 Fibonacci and Its Closed Form (Binet's Formula)

F(n) = F(n−1) + F(n−2), F(0) = 0, F(1) = 1. Characteristic equation r^2 − r − 1 = 0 gives the golden ratio roots φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 − √5)/2 ≈ −0.618. Solving for the constants:

F(n) = (φ^n − ψ^n)/√5

Since |ψ| < 1, ψ^n → 0 and F(n) is the nearest integer to φ^n/√5 — Fibonacci grows exponentially with base φ. This is why naive recursive fib takes Θ(φ^n) time, and why AVL trees have height ≤ 1.44·log2(n): the worst-case AVL tree is a Fibonacci tree.

8.5 Non-Homogeneous Recurrences

For a(n) = c·a(n−1) + f(n): general solution = homogeneous solution + one particular solution. Guess the particular solution by the shape of f(n): constant → constant, polynomial of degree d → polynomial of degree d, k^n → C·k^n (multiply by n if k is a characteristic root).

Worked mini-example: a(n) = 2a(n−1) + 3, a(0) = 1.

1. Homogeneous part: A·2^n. Particular: try constant c: c = 2c + 3 → c = −3.
2. General: a(n) = A·2^n − 3; a(0) = 1 gives A = 4.
3. a(n) = 2^(n+2) − 3. Verify: a(1) = 2·1 + 3 = 5 and 2^3 − 3 = 5. ✔

8.6 Common Mistakes & Applications

• A second-order recurrence needs two initial conditions; one is not enough.
• Repeated roots require the extra factor n — writing A·2^n + B·2^n (= (A+B)2^n) loses a degree of freedom.
• Sign errors when moving terms into the characteristic equation.
• Applications: solving T(n) = 2T(n/2) + cn (substitute n = 2^k) yields the Θ(n log n) bound for merge sort; recurrences model loan amortization, population growth, and dynamic-programming table sizes.

🎯 Exam Focus

1. Solve a(n) = 5a(n−1) − 6a(n−2), a(0) = 1, a(1) = 0.
2. Solve a(n) = 6a(n−1) − 9a(n−2), a(0) = 1, a(1) = 6 (repeated root).
3. Derive the closed form 2^n − 1 for the Tower of Hanoi and prove it by induction.
4. State Binet's formula and use φ ≈ 1.618 to estimate F(10). (Exact F(10) = 55.)
5. Formulate a recurrence for the number of ways to climb n stairs taking 1 or 2 steps at a time, and solve for n = 6.
6. Solve a(n) = 3a(n−1) + 2n with a(1) = 3 (find a particular solution of the form cn + d).