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

Solving Second-Order Linear Homogeneous Recurrences

Solve recurrences like a_n = c₁a_{n-1} + c₂a_{n-2} using the characteristic equation and distinct roots.

Solving Second-Order Linear Homogeneous Recurrences

What you'll learn: How to find an explicit formula for recurrence relations of the form a_n = c₁a_{n-1} + c₂a_{n-2} using the characteristic equation method.

The Core Idea

You've seen how recurrence relations define sequences recursively—each term depends on previous terms. But how do we find a closed-form formula that directly computes a_n without computing all prior terms?

For second-order linear homogeneous recurrences like a_n = c₁a_{n-1} + c₂a_{n-2}, we use the characteristic equation approach. The key insight: assume solutions have the form a_n = r^n for some constant r.

The Method

Step 1: Form the characteristic equation Substitute a_n = r^n into your recurrence:

  • r^n = c₁r^{n-1} + c₂r^{n-2}
  • Divide by r^{n-2}: r² = c₁r + c₂
  • Rearrange: r² - c₁r - c₂ = 0

Step 2: Solve for the roots Use the quadratic formula to find r₁ and r₂. When the roots are distinct (r₁ ≠ r₂), the general solution is:

a_n = A·r₁^n + B·r₂^n

where A and B are constants.

Step 3: Apply initial conditions Use given values (like a₀ and a₁) to solve for A and B, giving you the complete explicit formula.

Example

For the Fibonacci recurrence F_n = F_{n-1} + F_{n-2}:

  • Characteristic equation: r² - r - 1 = 0
  • Roots: r₁ = (1+√5)/2, r₂ = (1-√5)/2
  • Solution: F_n = A·r₁^n + B·r₂^n (apply F₀=0, F₁=1 to find A and B)

Key Takeaway: Second-order linear homogeneous recurrences with distinct characteristic roots have solutions of the form a_n = A·r₁^n + B·r₂^n, where r₁ and r₂ solve r² - c₁r - c₂ = 0.