Recurrence Relation definition
A recurrence relation connects terms of a sequence to terms at other indices, usually earlier ones.
Recurrence Relation in a picture
How it works
For example, aₙ = aₙ₋₁ + 3 says each term is three more than the preceding term. Starting values determine which sequence satisfies the relation. A relation that depends on two previous terms generally needs two starting values. A recurrence can also model algorithm cost. In T(n) = T(n/2) + 1, the one extra unit represents the work before solving a half-size subproblem.
Worked examples
Find a₂ if a₀ = 4 and aₙ = 2aₙ₋₁.
a₁ = 8 and a₂ = 16.
Does aₙ = aₙ₋₁ + 1 specify a unique sequence by itself?
No. Different starting values give different sequences.
If T(1) = 1 and T(n) = T(n/2) + 1 for powers of two, find T(8).
T(2) = 2, T(4) = 3, and T(8) = 4. The recurrence counts one unit per halving plus the base case.
Common mistake
State the starting index and values. The recurrence tells how terms relate, and the starting data determine the result.
Quick check
Can a recurrence use two earlier terms?
Show answer
Yes.
Does a recurrence always give a closed formula in n?
Show answer
No. It gives a relation, which may or may not be solved in closed form.
Sources
Flashcard
Recurrence Relation
Reveal the definition
A recurrence relation connects terms of a sequence to terms at other indices, usually earlier ones.
Effortless Math. “Recurrence Relation.” Math Dictionary.
