Recurrence Relations

A recurrence relation defines each term of a sequence using earlier terms, together with initial conditions.

• aₙ = aₙ₋₁ + 3, a₀ = 2 → 2, 5, 8, 11, … (arithmetic)
• aₙ = 2aₙ₋₁, a₀ = 1 → 1, 2, 4, 8, … (geometric)
• Fₙ = Fₙ₋₁ + Fₙ₋₂, F₀ = 0, F₁ = 1 → Fibonacci

#Modelling with recurrences

#Linear homogeneous recurrences with constant coefficients

Form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ.

Method for degree 2 (aₙ = c₁aₙ₋₁ + c₂aₙ₋₂):

1. Write the characteristic equation: r² − c₁r − c₂ = 0.
2. Find its roots.
   • Distinct roots r₁, r₂: aₙ = α·r₁ⁿ + β·r₂ⁿ.
   • Repeated root r: aₙ = (α + βn)·rⁿ.
3. Use the initial conditions to find α and β.

#Example 1: distinct roots

aₙ = aₙ₋₁ + 2aₙ₋₂, a₀ = 2, a₁ = 7.

Characteristic equation r² − r − 2 = 0 → (r − 2)(r + 1) = 0 → r = 2, −1. So aₙ = α·2ⁿ + β(−1)ⁿ.

a₀: α + β = 2. a₁: 2α − β = 7. Adding: 3α = 9 → α = 3, β = −1.

aₙ = 3·2ⁿ − (−1)ⁿ.

#Example 2: repeated root

aₙ = 6aₙ₋₁ − 9aₙ₋₂, a₀ = 1, a₁ = 6.

r² − 6r + 9 = 0 → (r − 3)² = 0 → r = 3 (double). So aₙ = (α + βn)3ⁿ.

a₀ = α = 1. a₁ = (1 + β)·3 = 6 → β = 1. aₙ = (1 + n)·3ⁿ.

#Example 3: Fibonacci (Binet's formula)

r² − r − 1 = 0 → r = (1 ± √5)/2. With F₀ = 0, F₁ = 1:

Fₙ = (φⁿ − ψⁿ)/√5, where φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 − √5)/2

So Fibonacci numbers grow like φⁿ — which is why naive recursive Fibonacci is exponential.

from math import sqrt

def by_recurrence(n, a0, a1, c1, c2):
    a, b = a0, a1
    for _ in range(n):
        a, b = b, c1 * b + c2 * a
    return a

phi, psi = (1 + sqrt(5)) / 2, (1 - sqrt(5)) / 2
print("n   rec1  3*2^n-(-1)^n   rec2  (1+n)3^n   fib  Binet")
for n in range(8):
    r1 = by_recurrence(n, 2, 7, 1, 2)
    r2 = by_recurrence(n, 1, 6, 6, -9)
    f = by_recurrence(n, 0, 1, 1, 1)
    print(f"{n:<3} {r1:<5} {3 * 2**n - (-1)**n:<13} {r2:<5} {(1 + n) * 3**n:<9} {f:<4} {round((phi**n - psi**n) / sqrt(5))}")

n   rec1  3*2^n-(-1)^n   rec2  (1+n)3^n   fib  Binet
0   2     2             1     1         0    0
1   7     7             6     6         1    1
2   11    11            27    27        1    1
3   25    25            108   108       2    2
4   47    47            405   405       3    3
5   97    97            1458  1458      5    5
6   191   191           5103  5103      8    8
7   385   385           17496 17496     13   13

#Non-homogeneous recurrences

For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + F(n), the solution is (homogeneous solution) + (one particular solution). For Tower of Hanoi, Hₙ = 2Hₙ₋₁ + 1 has homogeneous part α·2ⁿ and particular solution −1; with H₁ = 1, Hₙ = 2ⁿ − 1.

#Divide-and-conquer recurrences

Recurrences like T(n) = aT(n/b) + f(n) come from recursive algorithms. They are solved with the Master Theorem — see Solving Recurrences in Algorithms.