1. Recurrence Relations — Basics

A recurrence relation defines a sequence by expressing each term aₙ in terms of previous terms. Solving a recurrence means finding a closed-form (explicit) formula for aₙ in terms of n alone.

2. Linear Homogeneous Recurrences

A linear homogeneous recurrence with constant coefficients of order k:

2.1 Fibonacci — Full Solution

3. Non-Homogeneous Recurrences

A non-homogeneous linear recurrence: aₙ = c₁aₙ₋₁ + ... + cₖaₙ₋ₖ + f(n)

General solution = Homogeneous solution (aₙ^(h)) + Particular solution (aₙ^(p))

4. Master Theorem

Solves divide-and-conquer recurrences: T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1.

4.1 Master Theorem — Common Algorithm Recurrences

5. Substitution & Iteration Methods

5.1 Iteration (Unrolling)

Repeatedly substitute the recurrence into itself until a pattern emerges, then sum the resulting series.

5.2 Substitution (Guess and Verify)

Guess a closed-form, then verify by induction. Commonly used to confirm Master Theorem results or solve recurrences where the theorem doesn't apply.

6. Generating Functions

The ordinary generating function (OGF) of a sequence {a₀, a₁, a₂, ...} is: G(x) = ∑_n=0^∞ aₙxⁿ

Solving a recurrence with GF: Multiply both sides by xⁿ, sum over all valid n, express as G(x), solve algebraically for G(x), then use partial fractions to extract coefficients.

7. Worked Examples (GATE CS Level)

Example 1 — Characteristic Equation

Problem: Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1, a₁ = 4.

Characteristic equation: r² = 5r − 6 → r² − 5r + 6 = 0 → (r−2)(r−3) = 0

Roots: r₁ = 2, r₂ = 3 (distinct)

General solution: aₙ = A×2ⁿ + B×3ⁿ

a₀ = 1: A + B = 1

a₁ = 4: 2A + 3B = 4

Solving: from first equation A = 1−B; substitute: 2(1−B)+3B = 4 → 2+B = 4 → B = 2, A = −1

Example 2 — Master Theorem

Problem: Determine T(n) using the Master Theorem for: (a) T(n) = 4T(n/2) + n, (b) T(n) = 4T(n/2) + n², (c) T(n) = 4T(n/2) + n³.

For all three: a=4, b=2 → p = log₂4 = 2. So critical function is n² = n^{log_b a}.

(a) T(n) = 4T(n/2) + n: f(n)=n = O(n²⁻¹) = O(n^p−ε) with ε=1 → Case 1

(b) T(n) = 4T(n/2) + n²: f(n)=n² = Θ(n²) = Θ(n^p×log⁰n) → Case 2 (k=0)

(c) T(n) = 4T(n/2) + n³: f(n)=n³ = Ω(n²⁺¹) → check regularity: 4f(n/2) = 4(n/2)³ = n³/2 ≤ (1/2)n³ ✓ → Case 3

Example 3 — Non-Homogeneous Recurrence

Problem: Solve aₙ = 3aₙ₋₁ + 2ⁿ with a₀ = 1.

Homogeneous part: aₙ = 3aₙ₋₁ → characteristic root r = 3 → aₙ^(h) = A×3ⁿ

Particular solution: f(n) = 2ⁿ, and 2 is NOT a characteristic root → try aₙ^(p) = C×2ⁿ

Substitute: C×2ⁿ = 3×C×2ⁿ⁻¹ + 2ⁿ → C×2ⁿ = (3C/2)×2ⁿ + 2ⁿ

Divide by 2ⁿ: C = 3C/2 + 1 → C − 3C/2 = 1 → −C/2 = 1 → C = −2

General solution: aₙ = A×3ⁿ + (−2)×2ⁿ = A×3ⁿ − 2ⁿ⁺¹

Apply a₀=1: A×1 − 2 = 1 → A = 3

8. 5 Common Mistakes in Recurrence Relations

Mistake 1 — Forgetting to Verify the Regularity Condition in Master Theorem Case 3

What happens: Students apply Case 3 whenever f(n) looks "large" without checking af(n/b) ≤ cf(n).

Root cause: Case 3 needs both the growth condition AND the regularity condition. Without regularity, Case 3 may not apply.

Correct approach: For Case 3, always check: a×f(n/b) ≤ c×f(n) for some c<1 and large n.

Mistake 2 — Applying Master Theorem to Non-Divide-and-Conquer Recurrences

What happens: Students apply the Master Theorem to T(n)=T(n−1)+1 (which is O(n), not O(log n)).

Root cause: The Master Theorem only applies to T(n)=aT(n/b)+f(n) — the subproblem size is n/b (division), not n−k (subtraction).

Correct approach: For T(n)=T(n−k)+f(n), use iteration or substitution. T(n)=T(n−1)+1 = n (by telescoping).

Mistake 3 — Using Wrong Particular Solution Form When Root Collides

What happens: For aₙ = 2aₙ₋₁ + 3×2ⁿ, students try C×2ⁿ as particular solution — but 2 is a characteristic root, leading to 0=3×2ⁿ contradiction.

Root cause: When f(n)=sⁿ and s is a characteristic root of multiplicity m, multiply the guess by nᵐ.

Correct approach: Try C×n×2ⁿ instead. This is analogous to the case of repeated roots in ODEs.

Mistake 4 — Ignoring Initial Conditions When Solving Characteristic Equations

What happens: Students solve the characteristic equation and stop at the general form without applying initial conditions to find the constants.

Root cause: The characteristic equation gives a family of solutions parameterised by constants A₁,...,Aₖ. The specific solution requires using k initial conditions to pin down these constants.

Correct approach: Always substitute the initial values a₀, a₁, ..., aₖ₋₁ into the general solution and solve the resulting linear system for the constants.

Mistake 5 — Confusing p=log_ba with p=aˡᵒᵍᵇ

What happens: For T(n)=8T(n/2)+n², students write p=log₂8 correctly but then compare f(n)=n² with n² and think it's Case 2 — but log₂8=3, so n^p=n³ and n² grows slower → it's Case 1.

Root cause: Arithmetic error in computing log_ba, then comparing f(n) to the wrong power.

Correct approach: Carefully compute p=log_ba. For T(n)=8T(n/2)+n²: p=log₂8=3, n^p=n³. f(n)=n²=O(n³⁻¹) → Case 1 → T(n)=Θ(n³).

9. Frequently Asked Questions

Q1. What is the Master Theorem and when can it be applied?

The Master Theorem provides a closed-form solution for divide-and-conquer recurrences T(n)=aT(n/b)+f(n) (a≥1, b>1). The key quantity is p=log_ba — compare f(n) to n^p: (1) f slower than n^p → T=Θ(n^p); (2) f equal to n^p×log^kn → T=Θ(n^p×log^k+1n); (3) f faster than n^p (with regularity) → T=Θ(f(n)). It does NOT apply when: the subproblem size is n−k (not n/b), when f(n) falls in the "gap" between cases, or when the recurrence has variable coefficients.

Q2. How do you solve a linear homogeneous recurrence relation?

Four steps: (1) Write the characteristic equation by substituting aₙ=rⁿ and dividing by rⁿ⁻ᵏ. (2) Find all roots of the characteristic polynomial. (3) Write the general solution: for each distinct root rᵢ, add Aᵢrᵢⁿ; for each repeated root rᵢ of multiplicity m, add (B₀+B₁n+...+Bₘ₋₁nᵐ⁻¹)rᵢⁿ. (4) Use initial conditions to solve for all constants. This method works for any order-k recurrence and is the most systematic approach tested in GATE.

Q3. What is the recurrence for Fibonacci numbers and its closed form?

F(n)=F(n−1)+F(n−2), F(0)=0, F(1)=1. The characteristic equation r²−r−1=0 gives roots φ=(1+√5)/2≈1.618 (golden ratio) and ψ=(1−√5)/2≈−0.618. Binet's formula: F(n)=(φⁿ−ψⁿ)/√5. Since |ψ|<1, ψⁿ→0, so F(n) is the nearest integer to φⁿ/√5 for large n. This is why computing the n-th Fibonacci number naively takes exponential time but the closed form is O(log n) (via fast exponentiation of φ). GATE often asks for the order of growth: F(n)=Θ(φⁿ).

Q4. What is a generating function and how is it used to solve recurrences?

The ordinary generating function (OGF) of {a₀,a₁,...} is G(x)=Σaₙxⁿ — a formal power series encoding the entire sequence. To solve a recurrence: multiply the recurrence by xⁿ, sum over n, then express every sum in terms of G(x) and initial values. Solve the resulting equation algebraically for G(x). Decompose G(x) via partial fractions, then use known series (1/(1−rx)=Σrⁿxⁿ) to read off coefficients. Example: for F(n)=F(n−1)+F(n−2), the OGF satisfies G(x)=x/(1−x−x²) = x/((1−φx)(1−ψx)), leading directly to Binet's formula via partial fractions.