1
A recurrence plus initial conditions determines the sequence
Order k needs k initial values. With them every term is determined; without them the recurrence describes a family.
Lesson · Induction and Recursion · Recurrences
Recurrence Relations
A recurrence gives each term from previous ones. Setting one up is modelling; solving it means finding a closed form. This lesson does the first and prepares the second.
linear homogeneous, order k: aₙ = c₁aₙ₋₁ + … + c_k aₙ₋ₖ
nonhomogeneous: … + f(n)
k initial conditions determine the sequence completely
solving = finding a formula for aₙ that does not mention earlier terms
Vocabulary before technique
Core ideas
What this lesson establishes
Most of the difficulty in recurrences is setting them up. The solving techniques of “Solving Linear Recurrences” and “Divide-and-Conquer Recurrences” are mechanical once the recurrence is right.
2
Linear means the terms appear to the first power
aₙ = 2aₙ₋₁ + 3aₙ₋₂ is linear. aₙ = aₙ₋₁² and aₙ = aₙ₋₁ · aₙ₋₂ are not, and the techniques of “Solving Linear Recurrences” do not apply to them.
3
Homogeneous means no standalone term
The + f(n) in a nonhomogeneous recurrence is what makes the Tower of Hanoi 2aₙ₋₁ + 1 rather than 2aₙ₋₁.
The material
Setting up a recurrence
The classification, then four models built from scratch.
Definition · Recurrence relation
A recurrence relation expresses aₙ in terms of earlier terms of the sequence. Its order is how far back it reaches. Initial conditions supply the first terms outright.
Definition · Linear homogeneous with constant coefficients
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ⋯ + c_k aₙ₋ₖ, with the cᵢ constants and c_k ≠ 0. Linear: terms appear to the first power and are not multiplied together. Homogeneous: no term without an a in it.
Building recurrences
Example · Compound interest
A balance growing at r per period: aₙ = (1 + r)aₙ₋₁, with a₀ the initial deposit. First order, linear, homogeneous, and its solution a₀(1+r)ⁿ is immediate.
Example · Tower of Hanoi
Hₙ = 2Hₙ₋₁ + 1, H₁ = 1. First order, linear, nonhomogeneous — the +1 is the single move of the largest disc, and it is what makes the answer 2ⁿ − 1 rather than a power of 2.
Example · Rabbits, or bit strings
Fibonacci Fₙ = Fₙ₋₁ + Fₙ₋₂ is second order, linear, homogeneous. It counts more than rabbits: the number of binary strings of length n with no two consecutive 1s satisfies it too, because such a string either ends in 0 (any valid string of length n−1) or in 01 (any valid string of length n−2).
That derivation is the model for setting up a counting recurrence: split the objects by their last piece, and each part is counted by a smaller instance of the same problem. Getting the split right — exhaustive and non-overlapping — is the whole task.
Example · Codewords
How many strings of length n over {0,1,2} contain an even number of 0s? Let aₙ be that count. A valid string of length n is a valid string of length n−1 followed by 1 or 2, or an invalid one followed by 0. Since there are 3ⁿ⁻¹ strings in total, aₙ = 2aₙ₋₁ + (3ⁿ⁻¹ − aₙ₋₁) = aₙ₋₁ + 3ⁿ⁻¹, with a₁ = 2. Nonhomogeneous, with f(n) = 3ⁿ⁻¹.
Iteration: solving by unrolling
Before any technique, a recurrence can often be solved by unrolling it and spotting the pattern — then proving the guess by induction. That last step is not optional: unrolling produces a conjecture.
Hₙ = 2Hₙ₋₁ + 1
= 2(2Hₙ₋₂ + 1) + 1 = 4Hₙ₋₂ + 2 + 1
= 4(2Hₙ₋₃ + 1) + 3 = 8Hₙ₋₃ + 4 + 2 + 1
…
= 2ⁿ⁻¹H₁ + (2ⁿ⁻² + … + 2 + 1)
= 2ⁿ⁻¹ + 2ⁿ⁻¹ − 1 = 2ⁿ − 1
The geometric sum from “Induction with Sums and Products” finished it. Unrolling works well for first-order recurrences and becomes unmanageable for higher orders, which is why “Solving Linear Recurrences” exists.
Interactive
Recurrence and closed form
Iterated and solved, then compared
Method
Setting up a recurrence
Find the last decision; everything before it is a smaller instance.
1
Define aₙ precisely
"The number of …of length n". A vague definition produces a recurrence that counts something else.
2
Split by the last piece
Classify the objects by their final element or final move. Each class should correspond to a smaller instance.
3
Check the split is exhaustive and non-overlapping
Every object in exactly one class. Overlap double-counts; a gap undercounts, and neither shows up until the numbers are wrong.
4
Supply as many initial conditions as the order
A second-order recurrence needs two, and computing them by hand from the definition is where off-by-one errors surface.
Recurrences
Score 0 / 0Choose the answer you can justify.
Strings with no two consecutive 1s
Let aₙ be the number of binary strings of length n with no 11.
Split by the last character:
ends in 0: the first n−1 characters are any valid string → aₙ₋₁
ends in 1: the character before must be 0, and the first
n−2 are any valid string → aₙ₋₂
Exhaustive (a string ends in 0 or 1) and disjoint.
aₙ = aₙ₋₁ + aₙ₋₂
Initial conditions, by listing:
n = 1: 0, 1 a₁ = 2
n = 2: 00, 01, 10 a₂ = 3 (11 excluded)
Sequence: 2, 3, 5, 8, 13, 21, 34 … = Fₙ₊₂
Same recurrence as Fibonacci, different initial conditions, so the sequence is shifted. That is the general situation: the recurrence determines the shape of the solution and the initial conditions select which one, which is exactly what “Solving Linear Recurrences” formalises.
Common mistakes
1
Overlapping cases in the splitStrings counted in two classes are counted twice. Check by listing the small cases and comparing with the recurrence's prediction.
2
Wrong number of initial conditionsOrder k needs k of them. Fewer leaves the sequence undetermined; more may be inconsistent with the recurrence.
3
Treating an unrolled pattern as provedUnrolling produces a conjecture. The induction proof is what turns it into a solution, and “Cases, Counterexamples, and Writing a Proof” in Logic and Proof explains why that step is not a formality.
Check your understanding
✓
Finish when you can derive a recurrence and verify its first terms by hand.
Find a recurrence for the number of ways to tile a 2 × n strip with 1 × 2 dominoes, and check a₁ through a₄ by drawing them. You should get Fibonacci again, which is worth understanding rather than noticing.
Note: Recurrences are the discrete counterpart of differential equations, and the solution methods parallel each other closely: characteristic equations, homogeneous plus particular solutions, and the same trouble when a root of the characteristic equation collides with the forcing term.