Linear Homogeneous Recurrence Relations
What You'll Learn
You'll discover how to solve a special class of recurrence relations using characteristic equations—a powerful algebraic shortcut that transforms recursive patterns into closed formulas.
The Core Idea
A linear homogeneous recurrence relation with constant coefficients has the form:
aₙ = c₁·aₙ₋₁ + c₂·aₙ₋₂ + ... + cₖ·aₙ₋ₖ
where the coefficients c₁, c₂, ..., cₖ are constants, and each term depends only on previous terms (no extra functions or constants added—that's the "homogeneous" part).
Example: The Fibonacci sequence Fₙ = Fₙ₋₁ + Fₙ₋₂ is linear homogeneous with c₁ = 1, c₂ = 1.
The Characteristic Equation Approach
Instead of computing terms recursively, we look for solutions of the form aₙ = rⁿ for some constant r. Substituting into our recurrence:
rⁿ = c₁·rⁿ⁻¹ + c₂·rⁿ⁻² + ... + cₖ·rⁿ⁻ᵏ
Dividing through by rⁿ⁻ᵏ gives the characteristic equation:
rᵏ = c₁·rᵏ⁻¹ + c₂·rᵏ⁻² + ... + cₖ
or equivalently: rᵏ - c₁·rᵏ⁻¹ - c₂·rᵏ⁻² - ... - cₖ = 0
For Fibonacci: r² - r - 1 = 0, which solves to r = (1±√5)/2.
The general solution is then a linear combination of these roots: aₙ = A·r₁ⁿ + B·r₂ⁿ, where A and B are determined by initial conditions.
Why This Works
Think of rⁿ as a "growth pattern." The recurrence constrains how fast sequences can grow, and the characteristic equation finds all valid growth rates. Any solution is built from these fundamental patterns.
Key Takeaway: Linear homogeneous recurrence relations with constant coefficients can be solved by finding roots of their characteristic equation, transforming recursive definitions into explicit formulas.