Recurrence Relation Solver
Solve linear recurrence relations like the Fibonacci recurrence: the characteristic equation, its roots and the closed form, checked against the recurrence itself.
About the Recurrence Relation Solver
A linear recurrence aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ is solved by trying aₙ = rⁿ, which gives the characteristic equation r² = c₁r + c₂. Distinct roots give aₙ = A r₁ⁿ + B r₂ⁿ, a repeated root gives (A + Bn)rⁿ, and the constants come from a₀ and a₁. For Fibonacci the roots are (1 ± √5)/2, which gives Binet's formula.
With a right-hand side f(n), add a particular solution of the same form as f (multiplied by n when that form already solves the homogeneous part).
The formula
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ ⇒ r² − c₁r − c₂ = 0
- Distinct roots
- aₙ = A r₁ⁿ + B r₂ⁿ
- Repeated root
- aₙ = (A + Bn) rⁿ
Worked example
Fibonacci: aₙ = aₙ₋₁ + aₙ₋₂, a₀ = 0, a₁ = 1
- r² − r − 1 = 0, r = (1 ± √5)/2
- aₙ = (√5/5)((1 + √5)/2)ⁿ − (√5/5)((1 − √5)/2)ⁿ
Questions people ask
Is the formula checked?
Yes: the recurrence is run in exact fractions for 22 terms and the formula must reproduce every one.
What about higher orders?
This page covers order 2 (and order 1 with c₂ = 0).