Recurrence Relations
A recurrence relation defines a sequence where each term depends on previous terms. Recurrences naturally arise in algorithm analysis (divide-and-conquer, dynamic programming) and counting problems.
Definition and Examples
A recurrence has a formula relating aₙ to earlier terms and initial conditions. Examples: Fibonacci (aₙ = aₙ₋₁ + aₙ₋₂), factorial (aₙ = n · aₙ₋₁), Tower of Hanoi (Tₙ = 2Tₙ₋₁ + 1). The order of a recurrence is the number of previous terms it depends on.
Solving Linear Recurrences
A linear homogeneous recurrence with constant coefficients has the form aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + .... The characteristic equation replaces aₙ with rⁿ. For distinct roots r₁, r₂: aₙ = A·r₁ⁿ + B·r₂ⁿ. For repeated root r: aₙ = (A + Bn)·rⁿ. Constants are determined by initial conditions.
Non-homogeneous Recurrences
Non-homogeneous recurrences have an additional function: aₙ = c₁aₙ₋₁ + f(n). The solution is the general solution of the homogeneous part plus a particular solution. Methods include undetermined coefficients and variation of parameters.
The Master Theorem
The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n), common in divide-and-conquer algorithms. Three cases compare f(n) with n^(log_b a): Case 1: f is polynomially smaller → T = Θ(n^(log_b a)). Case 2: f is equal → T = Θ(n^(log_b a) log n). Case 3: f is polynomially larger → T = Θ(f(n)).
Recursion Tree Method
The recursion tree visualises the recurrence by drawing the work done at each level. Sum the work across all levels to get the total. This method provides intuition and can be used to guess a solution, which is then verified by substitution.
Generating Functions
A generating function represents a sequence as coefficients of a power series: G(x) = Σ aₙxⁿ. Operations on generating functions correspond to operations on sequences. They provide a powerful algebraic method for solving recurrences and counting problems.
Applications
Recurrences analyse algorithm complexity: merge sort (T(n) = 2T(n/2) + n → Θ(n log n)), binary search (T(n) = T(n/2) + 1 → Θ(log n)). Dynamic programming converts recursive formulations into iterative solutions. Counting problems like derangements and Catalan numbers use recurrences.
Summary
Recurrence relations are essential for analysing recursive algorithms and solving counting problems. The characteristic equation, Master Theorem, and generating functions provide systematic solution methods.