Solving linear recurrences
Counting and combinatorics (advanced) · Mathematics
Study notes
Q: Solve aₙ = 5aₙ₋₁ - 6aₙ₋₂ with a₀ = 1, a₁ = 4. Characteristic: r² = 5r - 6 → r²-5r+6 = 0 → r = 2, 3. General: aₙ = A·2ⁿ + B·3ⁿ. a₀ = 1: A+B = 1. a₁ = 4: 2A+3B = 4. From first B = 1-A: 2A+3-3A = 4 → A = -1, B = 2. Solution: aₙ = -2ⁿ + 2·3ⁿ. Check: a₂ = -4+18 = 14 = 5(4)-6(1) ✓!