Solving Linear Recurrences: Characteristic Equation Method

A linear recurrence defines each term of a sequence from earlier terms, like aₙ = 5aₙ₋₁ − 6aₙ₋₂. Given the initial conditions (the first values), the whole sequence is determined. The Fibonacci sequence Fₙ = Fₙ₋₁ + Fₙ₋₂ is the most famous example.

Computing term by term is slow and reveals no pattern. The characteristic equation method finds a closed form expressing aₙ directly in terms of n, so you can jump to the millionth term at once. For second-order linear recurrences with constant coefficients, the method is completely mechanical.

Key Concepts

• Linear recurrence: aₙ = p·aₙ₋₁ + q·aₙ₋₂ with constant coefficients p, q.
• Initial conditions: the starting values (e.g. a₀, a₁) that pick one specific sequence out of infinitely many.
• Characteristic equation: r² = p·r + q, or r² − p·r − q = 0. Its roots determine the form of the solution.
• Distinct roots r₁, r₂: general solution aₙ = α·r₁ⁿ + β·r₂ⁿ.
• Repeated root r: general solution aₙ = (α + β·n)·rⁿ.
• Scope: this method needs constant coefficients and a homogeneous equation.

Formulas

• Characteristic equation: for aₙ = p·aₙ₋₁ + q·aₙ₋₂, solve r² − p·r − q = 0.
• Distinct real roots: aₙ = α·r₁ⁿ + β·r₂ⁿ; find α, β from the two initial conditions.
• Repeated root r: aₙ = (α + β·n)·rⁿ; the extra factor n appears because rⁿ alone gives only one independent solution.
• Why it works: substituting aₙ = rⁿ and dividing by rⁿ⁻² yields exactly the characteristic equation.

Worked Example

Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1 and a₁ = 4.

• Characteristic equation: r² − 5r + 6 = (r − 2)(r − 3) = 0, so r₁ = 2, r₂ = 3.
• General solution: aₙ = α·2ⁿ + β·3ⁿ.
• Use a₀ = 1: α + β = 1.
• Use a₁ = 4: 2α + 3β = 4; with α = 1 − β this gives β = 2, α = −1.
• Closed form: aₙ = −2ⁿ + 2·3ⁿ.
• Verify: a₂ = −4 + 18 = 14, and 5·a₁ − 6·a₀ = 20 − 6 = 14. Also a₃ = −8 + 54 = 46 = 5·14 − 6·4. Both match.

Common Misconceptions

• "The recurrence alone determines the sequence." It does not. aₙ = 5aₙ₋₁ − 6aₙ₋₂ with different starting values gives a different sequence; α and β encode the initial conditions.
• "Repeated roots use the same formula." With r₁ = r₂ = r, α·rⁿ + β·rⁿ collapses to a single term, losing a degree of freedom. The correct form (α + β·n)·rⁿ restores it.
• "This only works for second order." The idea extends: third-order recurrences give cubic characteristic equations.

Real-World Applications

• Finance: loan balances and compound growth follow first-order linear recurrences; closed forms give payment formulas directly.
• Algorithm analysis: running times of recursive algorithms satisfy recurrences; solving them yields Big-O bounds.
• Combinatorics: counting tilings, binary strings without consecutive ones, and similar problems produces recurrences with neat closed forms.

To solve a second-order linear recurrence, write its characteristic equation, build the general solution from its roots (with the factor n for a repeated root), and fix the constants with the initial conditions. One mechanical method replaces endless term-by-term computation.