Questions: Solving Linear Recurrences: The Characteristic Equation

Question 1

After applying the characteristic equation method to a recurrence, a student finds the general solution aₙ = A(2ⁿ) + B(3ⁿ) and immediately announces that A = 1 and B = 1 without using the initial conditions. This is:

• A. Correct — for homogeneous recurrences, the constants are always 1 unless the roots are complex
• B. Wrong — the constants A and B must be determined by substituting the initial conditions into the general solution and solving the resulting linear system
• C. A valid shortcut when the characteristic roots are distinct positive integers
• D. Correct only if the initial conditions happen to be a₀ = 1 and a₁ = 5

Answer: (B)

The general solution contains undetermined constants that represent all solutions to the recurrence. The specific constants satisfying the given initial conditions are found by substituting those conditions (e.g., a₀ and a₁) into the general solution, producing a system of equations. Skipping this step means the solution does not match the actual sequence defined by the recurrence — it is a formula for the wrong sequence.

Question 2

The characteristic equation of a linear recurrence has a repeated root r = 4 (multiplicity 2). The general solution is:

• A. aₙ = A(4ⁿ), since both basis solutions are the same
• B. aₙ = A(4ⁿ) + B(n · 4ⁿ)
• C. aₙ = A(4ⁿ) + B(4²ⁿ), using the root and its square
• D. aₙ = A(4ⁿ) + B(4ⁿ⁻¹), shifting by one index

Answer: (B)

When the characteristic polynomial has a repeated root r, the two 'basis solutions' rⁿ and rⁿ are identical and cannot span all solutions — you cannot independently tune two constants if they always appear in the same ratio. The fix is to multiply the second basis solution by n, giving rⁿ and n·rⁿ as two linearly independent solutions. The general solution is then aₙ = Arⁿ + Bnrⁿ. This mirrors the method of undetermined coefficients for repeated roots in differential equations.

Question 3

The closed-form expression for the Fibonacci sequence, Fₙ = (φⁿ − ψⁿ)/√5, involves irrational numbers but produces an integer for every non-negative integer n.

• T. True
• F. False

Answer: True

This is one of the most striking facts about the Fibonacci closed form. φ = (1+√5)/2 and ψ = (1−√5)/2 are both irrational, yet their combination (φⁿ − ψⁿ)/√5 is always an integer. The irrational parts cancel exactly because A = 1/√5 and B = −1/√5 were determined by the initial conditions in a way that forces integer output. Verifying this numerically for the first several terms is a useful sanity check after deriving any closed form.

Question 4

The characteristic equation method mainly applies to second-order recurrences (those defined by the two previous terms).

• T. True
• F. False

Answer: False

The method extends naturally to any order. A degree-k linear homogeneous recurrence with constant coefficients yields a degree-k characteristic polynomial with k roots. The general solution is a linear combination of k basis solutions (one per root, with polynomial multipliers for repeated roots), and k initial conditions determine the k constants. The second-order case is simply the most commonly taught, not a fundamental limitation.

Question 5

Explain why assuming aₙ = rⁿ is the right starting point for solving a linear recurrence — why does this 'guess' lead to an exact method rather than just an approximation?

Model answer: Linear recurrences with constant coefficients shift and scale sequences in a way that preserves exponential form. If aₙ = rⁿ, then aₙ₋₁ = rⁿ⁻¹ and aₙ₋₂ = rⁿ⁻², so substituting into cₙ = c₁aₙ₋₁ + c₂aₙ₋₂ gives rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻², which factors completely into a polynomial equation in r. Exponentials are eigenfunctions of the shift operator, so substituting one never introduces new terms — it just yields a polynomial whose roots are the exact building blocks of all solutions.

The reason the method is exact (not approximate) is that exponentials are closed under the operations the recurrence applies: scaling and shifting. Any function with this property would work. The characteristic equation approach turns a functional equation (the recurrence) into an algebraic equation (the polynomial), which can then be solved exactly with standard tools like the quadratic formula.