For the recurrence aₙ = 5aₙ₋₁ − 6aₙ₋₂, what is the characteristic equation?
Ar² − 5r + 6 = 0
Br² + 5r − 6 = 0
Cr³ − 5r² + 6r = 0
Dr = 5r − 6
Substituting aₙ = rⁿ gives rⁿ = 5rⁿ⁻¹ − 6rⁿ⁻². Dividing both sides by rⁿ⁻²: r² = 5r − 6, which rearranges to r² − 5r + 6 = 0. The coefficients in the characteristic polynomial match the recurrence coefficients with alternating signs. Option B has wrong signs; option C has wrong degree; option D is just the recurrence restated, not a polynomial in r.
Question 2 Multiple Choice
The characteristic equation of a recurrence has two distinct roots r₁ = 2 and r₂ = 3. What is the general solution?
Aaₙ = A · 2ⁿ + B · 3ⁿ
Baₙ = A · 2 + B · 3
Caₙ = (A + B) · 5ⁿ
Daₙ = A · 2ⁿ · B · 3ⁿ
When the characteristic equation has k distinct roots r₁, r₂, …, rₖ, the general solution is a linear combination aₙ = A₁r₁ⁿ + A₂r₂ⁿ + … + Aₖrₖⁿ. The constants A and B are determined by initial conditions. Option B forgets the exponent n entirely; option C incorrectly adds the bases (you cannot combine exponentials that way); option D multiplies instead of adding — exponential solutions superpose, they don't multiply.
Question 3 True / False
If the characteristic equation of a recurrence has a repeated root r = 2 (multiplicity 2), the general solution is aₙ = (A + Bn) · 2ⁿ.
TTrue
FFalse
Answer: True
Repeated roots require a modified solution. When r is a root of multiplicity m, the general solution includes terms rⁿ, n·rⁿ, n²·rⁿ, …, nᵐ⁻¹·rⁿ. For a double root r = 2, this gives aₙ = A·2ⁿ + Bn·2ⁿ = (A + Bn)·2ⁿ. This modification is necessary because simply writing aₙ = A·2ⁿ + B·2ⁿ = (A+B)·2ⁿ only gives one free constant, which is insufficient to satisfy two initial conditions.
Question 4 True / False
The Fibonacci sequence can seldom be expressed as a closed-form formula because its characteristic equation has irrational roots.
TTrue
FFalse
Answer: False
Binet's formula Fₙ = (φⁿ − ψⁿ)/√5, where φ = (1+√5)/2 and ψ = (1−√5)/2, IS a valid closed-form despite the irrational numbers. The irrationals cancel perfectly at every integer n, always producing an integer result. The existence of irrational roots does not prevent a closed-form — it just means the formula contains irrational constants that happen to combine to integers.
Question 5 Short Answer
Why is the substitution aₙ = rⁿ the key trick for solving linear homogeneous recurrences? What does this assumption accomplish?
Think about your answer, then reveal below.
Model answer: Substituting aₙ = rⁿ into the recurrence converts a functional equation (a rule connecting sequence terms) into a polynomial equation in r. Every rⁿ factor can be divided out, leaving a polynomial whose roots tell you exactly which exponential bases appear in the solution. The trick works because exponential sequences are the natural eigenfunctions of the shift operator — just as e^(rx) solves linear ODEs with constant coefficients, rⁿ solves linear recurrences with constant coefficients.
This is the discrete analogue of solving differential equations by guessing e^(rx). The reason it works is that linear recurrences are linear maps on sequences, and exponential sequences are eigenvectors of the shift operation. Once you have the roots, the general solution is a linear combination — satisfying superposition — and initial conditions pin down the constants. Without this substitution, converting a recursive definition to a direct formula would require much more complex techniques.