Recurrence Relation Solver — aₙ = p·aₙ₋₁ + q·aₙ₋₂

How it works

aₙ = p·aₙ₋₁ + q·aₙ₋₂ → characteristic equation r² − p·r − q = 0 · distinct roots r₁, r₂: aₙ = α·r₁ⁿ + β·r₂ⁿ · double root r: aₙ = (α + βn)·rⁿ · complex roots ρe^(±iθ): aₙ = ρⁿ(α cos nθ + β sin nθ) · α, β from a₀ and a₁

A second-order linear homogeneous recurrence with constant coefficients is solved by guessing aₙ = rⁿ, which turns it into the characteristic equation r² = p·r + q. Its roots give the shape of the general solution — powers of two distinct roots, n·rⁿ for a repeated root, or a damped or growing oscillation for complex roots — and the two initial terms fix the constants α and β (Rosen, Discrete Mathematics and Its Applications, §8.2). When the roots are rational the closed form is exact; the table and the nth term are computed exactly from the recurrence itself.

Worked example

aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1 and a₁ = 4. The characteristic equation r² − 5r + 6 = 0 has roots 2 and 3, so aₙ = α·2ⁿ + β·3ⁿ. From a₀: α + β = 1 and a₁: 2α + 3β = 4, so β = 2 and α = −1: aₙ = −2ⁿ + 2·3ⁿ. Then a₁₀ = −1,024 + 2 × 59,049 = 117,074.

Sources: Rosen — Discrete Mathematics and Its Applications, §8.2 Solving Linear Recurrence Relations · Wolfram MathWorld — Linear Recurrence Equation

Frequently asked questions