Solving Linear Recurrences

Key idea

Use the characteristic equation.

In depth

For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, solve the characteristic equation r² = c₁r + c₂. Distinct roots r₁, r₂ give aₙ = Ar₁ⁿ + Br₂ⁿ; a repeated root r gives (A + Bn)rⁿ. Match initial values to find A and B.

Worked example

aₙ = 5aₙ₋₁ − 6aₙ₋₂, a₀ = 1, a₁ = 4: roots 2, 3; aₙ = A·2ⁿ + B·3ⁿ with A + B = 1 and 2A + 3B = 4, so B = 2, A = −1 and aₙ = 2·3ⁿ − 2ⁿ.

Formula

Real-world uses

• Finding a formula for a sequence in finance, biology and algorithm analysis

Common mistake

Forgetting the n factor for repeated roots.

How to learn this

1. Read the key idea and say it in your own words.
2. Work through the worked example, then try a similar problem.
3. Use the interactive lesson’s visual and mini-quiz to check the pattern.

Frequently asked questions

Expand all Collapse all

Related expert topics in Discrete Math & Number Theory

• Strong Induction – Assume all earlier cases to prove the next.
• Well-Ordering Principle – Every nonempty set of positive integers has a least element.
• Partial Orders – Reflexive, antisymmetric, transitive relations.
• Cardinality of Sets – Comparing sizes of infinite sets.
• Countable and Uncountable Sets – ℕ and ℚ are countable; ℝ is not.
• Cantor’s Diagonal Argument – Proof that real numbers are uncountable.