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

Linear Homogeneous Recurrence Relations

Introduce linear homogeneous recurrences with constant coefficients and their characteristic equation approach.

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.