Discrete Math · Undergraduate
Recurrence Relations and How to Solve Them
Quick answer
A recurrence relation defines each term of a sequence from earlier terms, together with starting values: the Fibonacci numbers satisfy Fₙ = Fₙ₋₁ + Fₙ₋₂. Computing terms one by one suits a computer but is slow by hand. A linear recurrence with constant coefficients, such as aₙ = 5aₙ₋₁ − 6aₙ₋₂, has a closed form found by trying aₙ = rⁿ: the roots of the characteristic equation give the building blocks, and the starting values fix the constants.
What you'll learn
- Compute terms of a sequence from a recurrence
- Set up a recurrence for a counting problem
- Solve linear recurrences with the characteristic equation
- Handle a repeated characteristic root
Defining a sequence by its past
A recurrence relation gives each term from earlier ones. The arithmetic and geometric sequences are the simplest: and . The Fibonacci numbers use two earlier terms:
giving . A recurrence needs as many starting values as the number of earlier terms it uses.
Many counting problems lead to recurrences. In the Tower of Hanoi, disks must move between pegs, one at a time, never putting a larger disk on a smaller. To move disks, move the top aside, move the largest, then move the back on top: , with .
The characteristic equation
A linear recurrence with constant coefficients, such as , can be solved in closed form. Try :
Both and satisfy the recurrence, and so does any combination . The starting values pick and .
Why combinations work
The recurrence is linear: if two sequences each satisfy it, so does any sum of multiples of them, since the recurrence only adds and scales terms. So the solutions form a two-dimensional family, and two independent solutions build all of them. This is exactly the structure of second-order differential equations, with in place of . A repeated root needs a second solution, and as there, multiplying by provides it: .
Worked examples
Common mistakes
Practice problems
-
Solve with .
Answer
Full solution
Each term triples the last: a geometric sequence.
-
Solve with .
Answer
Full solution
Each term adds : an arithmetic sequence.
-
Find .
Answer
Full solution
Continue from , : .
-
Solve with , .
Answer
Full solution
. Then and give .
-
How many moves does the Tower of Hanoi need for disks?
Answer
Full solution
.
-
Solve with , .
Answer
Full solution
gives a double root. and , so .
-
Let count binary strings of length with no two s in a row. Explain why , and find .
Answer
Full solution
A valid string ends in (any valid string of length , then ) or in (any valid string of length , then ). With and : .
-
A student solves as and cannot fit , . Why?
Answer
With a double root, the second solution is ; the form must be .
Full solution
has one free constant, but two starting values need two.
Frequently asked questions
What is a recurrence relation?
A rule that gives each term of a sequence from earlier terms, such as aₙ = aₙ₋₁ + 3, together with enough starting values to begin.
How do you solve aₙ = c₁aₙ₋₁ + c₂aₙ₋₂?
Try aₙ = rⁿ to get the characteristic equation r² = c₁r + c₂. With distinct roots r₁, r₂, the solution is aₙ = A·r₁ⁿ + B·r₂ⁿ, and the starting values fix A and B.
What if the characteristic equation has a repeated root?
With a double root r, the solution is aₙ = (A + Bn)rⁿ.
What is the closed form of the Tower of Hanoi?
Moving n disks takes hₙ = 2hₙ₋₁ + 1 moves, with h₁ = 1, and the closed form is hₙ = 2ⁿ − 1.
How are recurrences like differential equations?
Both describe change step by step, and linear ones with constant coefficients are solved the same way: try an exponential, solve a characteristic equation, and combine the solutions.