Course contentsShow
← Mathematics
Lesson 2632 of 3,12152. CombinatoricsFree lesson

Higher-Order Linear Homogeneous Recurrences

Extend the characteristic equation method to recurrences of order three or higher with multiple roots.

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 r appears once: contribute A·rⁿ to the general solution
  • If root r appears 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.