Key takeaways
- A recurrence relation defines each term of a sequence from earlier terms; with enough initial conditions it determines the sequence completely.
- For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, solve the characteristic equation r² = c₁r + c₂; distinct roots r₁, r₂ give aₙ = A·r₁ⁿ + B·r₂ⁿ.
- A repeated root r gives aₙ = (A + Bn)rⁿ.
- Use the initial conditions to find the constants, then check the formula against a computed term.
- To set up a recurrence for a counting problem, split the objects of size n by what happens at the first or last step.
A recurrence relation describes a sequence by saying how each term follows from the ones before it. "Each year the population doubles and 100 are added." "Each Fibonacci number is the sum of the previous two." Recurrences are the natural way to describe anything built step by step, and Levin's Discrete Mathematics: An Open Introduction notes that it is often easier to find a recursive definition than a closed formula.
This guide covers the two halves of working with them: setting one up from a problem, and solving it to get a closed-form formula.
The vocabulary
- A recurrence relation gives aₙ in terms of earlier terms: aₙ = 2aₙ₋₁ + 1.
- Initial conditions give the first term or terms: a₁ = 1.
- A closed form gives aₙ directly: aₙ = 2ⁿ − 1.
A recurrence that reaches back k terms needs k initial conditions. aₙ = aₙ₋₁ + aₙ₋₂ needs two, which is why the Fibonacci sequence is defined by F₀ = 0 and F₁ = 1, the convention in Levin's Discrete Mathematics: An Open Introduction.
Setting up a recurrence
The method: think about how an object of size n is built from smaller ones, usually by looking at the first or last step.
Tower of Hanoi. Moving n discs from one peg to another, never placing a larger disc on a smaller one, requires moving the top n − 1 discs out of the way, moving the largest disc, and moving the n − 1 discs back on top. So the minimum number of moves satisfies
Hₙ = 2Hₙ₋₁ + 1, with H₁ = 1.
Bit strings with no two consecutive 1s. Let bₙ count them. A valid string of length n either ends in 0, preceded by any valid string of length n − 1, or ends in 01, preceded by any valid string of length n − 2. So
bₙ = bₙ₋₁ + bₙ₋₂, with b₁ = 2 (0, 1) and b₂ = 3 (00, 01, 10).
The sequence runs 2, 3, 5, 8, 13, …, Fibonacci numbers shifted along. Our guide to Fibonacci and recursive sequences covers where else that sequence turns up.
Solving: linear, homogeneous, constant coefficients
The type solved in this guide, second-order linear with constant coefficients, has the form
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂,
with constants c₁ and c₂. Levin's book calls the method below the characteristic root technique, and Applied Discrete Structures develops the same method for finite order linear relations.
Step 1: guess aₙ = rⁿ. Substituting gives rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻², and dividing by rⁿ⁻² leaves the characteristic equation
r² − c₁r − c₂ = 0.
Step 2: find the roots. If they are distinct, r₁ and r₂, the general solution is
aₙ = A·r₁ⁿ + B·r₂ⁿ.
Step 3: fit the initial conditions to find A and B.
Worked example. Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1, a₁ = 4.
- Characteristic equation: r² − 5r + 6 = 0, so (r − 2)(r − 3) = 0 and r = 2, 3.
- General solution: aₙ = A·2ⁿ + B·3ⁿ.
- n = 0: A + B = 1. n = 1: 2A + 3B = 4. So B = 2 and A = −1.
- Closed form: aₙ = 2·3ⁿ − 2ⁿ.
Check a term the recurrence computes directly: a₂ = 5 × 4 − 6 × 1 = 14, and the formula gives 2 × 9 − 4 = 14. Always do this; it catches an arithmetic slip in step 3 at once.
Repeated roots
If the characteristic equation has a double root r, the solution rⁿ alone is not enough, and the general solution becomes
aₙ = (A + Bn)rⁿ.
Worked example. aₙ = 4aₙ₋₁ − 4aₙ₋₂, with a₀ = 1 and a₁ = 6.
- r² − 4r + 4 = (r − 2)² = 0, a double root at 2.
- aₙ = (A + Bn)2ⁿ. n = 0 gives A = 1; n = 1 gives (1 + B)·2 = 6, so B = 2.
- aₙ = (1 + 2n)2ⁿ. Check: a₂ = 4 × 6 − 4 × 1 = 20 and (1 + 4) × 4 = 20.
Adding a constant term
A recurrence such as Hₙ = 2Hₙ₋₁ + 1 is non-homogeneous because of the + 1. Solve it in two parts.
- A particular solution. Try a constant c: c = 2c + 1 gives c = −1.
- The homogeneous part. Hₙ = 2Hₙ₋₁ has solution A·2ⁿ.
- Combine and fit. Hₙ = A·2ⁿ − 1. With H₁ = 1, 2A − 1 = 1, so A = 1.
So the Tower of Hanoi needs 2ⁿ − 1 moves: 7 for three discs, 1,023 for ten. You can confirm a guessed closed form like this with a proof by induction, and when a recurrence calls on two earlier terms, the proof uses strong induction.
The Fibonacci closed form
For Fₙ = Fₙ₋₁ + Fₙ₋₂, the characteristic equation r² − r − 1 = 0 has roots φ = (1 + √5)/2 and ψ = (1 − √5)/2. Fitting F₀ = 0 and F₁ = 1 gives Binet's formula,
Fₙ = (φⁿ − ψⁿ)/√5.
Since |ψ| < 1, the second term shrinks quickly, so Fₙ is the nearest integer to φⁿ/√5, and the sequence grows by a factor of about 1.618 each step.
Recurrences in algorithm analysis
Divide-and-conquer algorithms give a different family. An algorithm that splits a problem of size n into two halves, solves each half, and combines the results with n further steps satisfies T(n) = 2T(n/2) + n. This is not a constant-coefficient recurrence in n, so characteristic roots do not apply directly; unrolling it for n a power of 2 with T(1) = 0 gives T(n) = n log₂ n (for example T(8) = 24), the kind of growth rate expressed in big-O notation.
For recurrences the characteristic method cannot handle, and for a second route to the ones it can, see generating functions.
Discrete Math: Study & Quiz has a recurrences unit, with lessons, knowledge checks and topic quizzes. It belongs to our education app collection; the discrete math hub lists the neighbouring guides.
Good to know
Frequently asked questions
What is a recurrence relation?
How do you solve a linear recurrence with constant coefficients?
What if the characteristic equation has a repeated root?
How do I handle a constant term, as in aₙ = 2aₙ₋₁ + 1?
Sources
- Solving Recurrence Relations (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
- Recurrence Relations (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Recurrence Relation (opens in a new tab)Wolfram MathWorld — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.