Questions: Solving Linear Recurrence Relations via Characteristic Equations

Question 1

The recurrence a(n) = 5a(n−1) − 6a(n−2) has which characteristic equation?

• A. x² = 5x − 6
• B. x² − 5x + 6 = 0
• C. x² + 5x − 6 = 0
• D. 5x² − x − 6 = 0

Answer: (B)

Substitute a(n) = r^n into the recurrence: r^n = 5r^(n−1) − 6r^(n−2). Divide by r^(n−2) to get r² = 5r − 6, then rearrange: r² − 5r + 6 = 0. The characteristic polynomial is built by moving all terms to one side, with the coefficient of a(n) term (1) on the leading power and the coefficients of a(n−k) terms contributing with alternating sign. Option A is the equation before rearranging — it's equivalent but not in standard polynomial form. Options C and D have sign errors.

Question 2

The characteristic equation of a recurrence has r = 3 as a root of multiplicity 2. What is the general solution contributed by this root?

• A. A · 3^n
• B. A · 3^n + B · 3^n
• C. A · 3^n + B · n · 3^n
• D. A · n · 3^n + B · n² · 3^n

Answer: (C)

A root r of multiplicity m contributes m linearly independent solution terms: r^n, n·r^n, n²·r^n, …, n^(m−1)·r^n. For r = 3 with multiplicity 2, the two independent solutions are 3^n and n·3^n, so the general contribution is A·3^n + B·n·3^n. Option A only has one term — not enough free constants for multiplicity 2. Option B looks like two terms but A·3^n + B·3^n = (A+B)·3^n, which is really just one free constant. Option D skips the plain 3^n term entirely.

Question 3

The general solution to a second-order homogeneous linear recurrence always requires exactly two free constants determined by initial conditions.

• T. True
• F. False

Answer: True

The set of all solutions to a k-th order homogeneous linear recurrence forms a k-dimensional vector space. For k = 2, this means any solution is a linear combination of exactly 2 linearly independent basis solutions, giving 2 free constants. The initial conditions a(0) and a(1) provide 2 equations that uniquely determine those constants — no more, no less. This parallels second-order linear ODEs, which also have 2-dimensional solution spaces.

Question 4

If r = 2 is a repeated root of multiplicity 3, the general solution contribution from this root is A·2^n + B·n·2^n.

• T. True
• F. False

Answer: False

A root of multiplicity 3 requires three independent terms: 2^n, n·2^n, and n²·2^n. The general contribution is A·2^n + B·n·2^n + C·n²·2^n, with three free constants. Only including two terms would give a 2-dimensional subspace when the root contributes a 3-dimensional one — the solution would miss an entire family of valid sequences, and the constants determined by initial conditions would generally be wrong.

Question 5

Why does guessing a(n) = r^n lead to a useful solution method for homogeneous linear recurrences?

Model answer: Because substituting r^n into a linear recurrence with constant coefficients converts it from a functional equation over sequences to a polynomial equation in r. Dividing out a common factor of r^(n−k) leaves a polynomial whose roots are exactly the values of r that make a(n) = r^n a valid solution. Since the recurrence is linear, any linear combination of valid solutions is also valid, so the roots of the characteristic polynomial generate a full basis for the solution space.

The key leverage is that r^n is an 'eigenfunction' of the shift operator — multiplying n by a constant shifts the sequence by a fixed ratio. This makes the coefficient structure of the recurrence become multiplicative in r rather than recursive in n, collapsing an infinite-dimensional recurrence to a finite-degree polynomial. This is the same reason exponentials are eigenfunctions of linear ODEs with constant coefficients.