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.