Recurrence relations
Objective. Solve elementary linear recurrences.
- 1. Learn
- 2. Worked example
- 3. Practice
- 4. Feedback
- 5. Continue
Learn: the key idea
A recurrence relation defines each term of a sequence in terms of previous terms, such as aₙ = aₙ₋₁ + aₙ₋₂ for the Fibonacci sequence, and solving it means finding an explicit closed-form formula for aₙ. For a linear homogeneous recurrence with constant coefficients like aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, the method is to find the characteristic equation x² = c₁x + c₂, solve for its roots, and combine them as aₙ = Ar₁ⁿ + Br₂ⁿ when the roots are distinct, fixing A and B using the initial conditions. For aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1 and a₁ = 4, the characteristic equation x² − 5x + 6 = 0 factors as (x−2)(x−3) = 0, giving roots 2 and 3, and the initial conditions determine A = 2, B = −1.
Worked example
Solve the recurrence relation aₙ = 3aₙ₋₁ with a₀ = 2 to find a closed-form formula for aₙ.
- 1Recognise this as a simple linear recurrence with constant ratio 3.
- 2Write the general geometric form: aₙ = a₀ × rⁿ where r = 3.
- 3Substitute the initial condition a₀ = 2 into this form.
- 4State the closed-form expression for aₙ.
Answer: aₙ = 2(3ⁿ)
Concept mastery
Based on your past attempts at this lesson — the question types to practise again come first.
Complete a practice set to see your concept breakdown here.
Practice
Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.
Start practisingCommon mistake. Students write the closed-form solution using only one root of the characteristic equation when it has two distinct roots; both root terms are needed, with coefficients fixed afterwards by the initial conditions.
Your progress
Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.
0 of 5 steps complete
Your place saves automatically as you read.