Higher-Order Linear Homogeneous Recurrences
What you'll learn: How to solve recurrence relations of order three or higher, including those with repeated roots in their characteristic equations.
The Core Idea
You've mastered second-order recurrences like a_n = c₁·a_{n-1} + c₂·a_{n-2}. Now we extend this to higher orders: recurrences like a_n = c₁·a_{n-1} + c₂·a_{n-2} + c₃·a_{n-3} (third-order) or even beyond.
The characteristic equation method still works! For a third-order recurrence, you get a cubic equation; for fourth-order, a quartic, and so on.
Handling Multiple Roots in Higher Orders
Just as with second-order recurrences, repeated roots require special treatment:
- If root
rappears once: contributeA·rⁿto the general solution - If root
rappears k times (multiplicity k): contribute(A₁ + A₂·n + A₃·n² + ... + A_k·n^(k-1))·rⁿ
Example: For a_n = 6a_{n-1} - 12a_{n-2} + 8a_{n-3}, the characteristic equation is:
r³ - 6r² + 12r - 8 = 0
This factors as (r - 2)³ = 0, giving root r = 2 with multiplicity 3.
General solution: a_n = (A + B·n + C·n²)·2ⁿ
The initial conditions determine constants A, B, and C.
Why the n-multipliers?
Think of it like this: repeated roots would normally give you the "same" solution multiple times. Multiplying by powers of n (1, n, n², ...) creates linearly independent solutions—different enough to span the solution space.
Key Takeaway: Higher-order recurrences use the same characteristic equation method, but repeated roots of multiplicity k contribute a polynomial of degree (k-1) in n, multiplied by the exponential term.