3.5Recurrence relations
The idea
A recurrence relation defines a sequence from earlier terms. For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ you solve the characteristic equation r² = c₁r + c₂ and combine the roots.
Think of it like this: Rabbits breeding: each month is the sum of the last two, and the roots of r² = r + 1 tell the long-run growth rate.
Why it exists
GATE gives you a recurrence and asks for a term, the closed form, or the growth; the method is the same each time.
How it works
- Write r² − c₁r − c₂ = 0 and find the roots.
- Distinct roots: aₙ = A r₁ⁿ + B r₂ⁿ. Repeated root r: aₙ = (A + Bn) rⁿ.
- Use the two initial values to solve for A and B.
- A constant forcing term adds a constant particular solution (when 1 is not a root).
- Often it is quickest to unroll: compute a few terms and spot the pattern.
Worked example: aₙ = 2aₙ₋₁ + 1, a₀ = 0 (Tower of Hanoi)
Terms 0, 1, 3, 7, 15, … so aₙ = 2ⁿ − 1. The lab confirms it: roots 2, particular solution −1.
Now play with it
- →Load Fibonacci and see the golden ratio 1.618 as a root.
- →Load "a(n) = 4a(n−1) − 4a(n−2)" and see the repeated root 2 give (A + Bn)·2ⁿ.
| Recurrence | Solution | Growth |
|---|---|---|
| a(n) = a(n−1) + c | a(0) + cn | linear |
| a(n) = c·a(n−1) | a(0)·cⁿ | exponential |
| a(n) = a(n−1) + n | a(0) + n(n+1)/2 | quadratic |
| a(n) = 2a(n−1) + 1 | 2ⁿ(a(0)+1) − 1 | exponential |
| a(n) = a(n−1) + a(n−2) | Fibonacci, φⁿ/√5 | 1.618ⁿ |
| a(n) = 2a(n−1) − a(n−2) | A + Bn | linear (repeated root 1) |
For T(n) = aT(n/b) + f(n) use the Master theorem (see the Algorithms subject).
Check yourself
The characteristic equation of aₙ = 5aₙ₋₁ − 6aₙ₋₂ has roots
Exam notes (the dense version)
Linear homogeneous with constant coefficients aₙ = c₁aₙ₋₁ + c₂aₙ₋₂: characteristic equation r² − c₁r − c₂ = 0. Distinct roots: aₙ = A r₁ⁿ + B r₂ⁿ. Repeated root: (A + Bn) rⁿ. Fit A and B to the initial values. A constant forcing term adds a particular solution. Famous ones: Fibonacci, Tower of Hanoi T(n) = 2T(n−1) + 1 = 2ⁿ − 1. Divide-and-conquer recurrences use the Master theorem.
Previous year questions: Combinatorics & Recurrences (17)
PYQs are grouped by topic, so this is the full set for Combinatorics & Recurrences; try the ones that match this subtopic. Open all 17 on the topic page.