Recurrence Relations

Definition

Recurrence Relation

A recurrence relation defines each term of a sequence using previous terms. It consists of: 1. A recursive formula: aₙ = f(aₙ₋₁, aₙ₋₂, ...) 2. Initial conditions: specific values for the first few terms.

Example: The Fibonacci sequence: F(n) = F(n-1) + F(n-2) with F(0) = 0, F(1) = 1.

Example

Tower of Hanoi

The Tower of Hanoi with n disks requires T(n) moves where: T(n) = 2T(n-1) + 1, T(1) = 1.

T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 15. The closed-form solution is T(n) = 2ⁿ - 1.

Definition

Linear Homogeneous Recurrence

A linear homogeneous recurrence of degree k has the form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

To solve, find the characteristic equation: rᵏ - c₁rᵏ⁻¹ - c₂rᵏ⁻² - ... - cₖ = 0

The roots determine the closed-form solution.

Example

Solving the Fibonacci Recurrence

F(n) = F(n-1) + F(n-2). Characteristic equation: r² - r - 1 = 0.

Roots: r = (1 ± √5)/2. Let φ = (1+√5)/2 and ψ = (1-√5)/2.

General solution: F(n) = Aφⁿ + Bψⁿ. Using F(0) = 0, F(1) = 1: A = 1/√5, B = -1/√5.

Closed form: F(n) = (φⁿ - ψⁿ)/√5. (Binet's formula)

Note

Recurrences in Computer Science

Recurrence relations arise naturally in algorithm analysis: • Binary search: T(n) = T(n/2) + O(1) → O(log n) • Merge sort: T(n) = 2T(n/2) + O(n) → O(n log n) • The Master Theorem provides a general method for solving divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).