Two-term recurrences with a repeated root

When you reach for it

The rule

has characteristic equation x^2 - c_1 x - c_2 = 0, as in Solving and checking a two-term recurrence (written here in the letter x, so that r can name the root). Its discriminant is c_1^2 + 4c_2 (The discriminant and the number of real solutions). When that is 0, the equation has only one root, a double root (or repeated root) \displaystyle r = \frac{c_1}{2}, and the quadratic is (x - r)^2 = x^2 - 2rx + r^2. Comparing coefficients, c_1 = 2r and c_2 = -r^2. So every rule with a double root has the form

with r \ne 0 because c_2 \ne 0. The distinct-roots theorem of Solving and checking a two-term recurrence needs two different roots, so it says nothing about these rules. Reach for this move whenever c_1^2 + 4c_2 = 0, as in a_n = 6a_{n-1} - 9a_{n-2}, where 6^2 + 4(-9) = 0 and x^2 - 6x + 9 = (x - 3)^2.

The procedure

One power is not enough

The sequence r^n is still a solution, since r is a characteristic root. But the family the distinct-roots method would write, Ar^n + Br^n = (A + B)r^n, has only one free constant, C = A + B. At n = 0 and n = 1 it gives a_0 = C and a_1 = Cr, so it fits only those starting values with a_1 = r\,a_0. For a_n = 6a_{n-1} - 9a_{n-2} with a_0 = 2 and a_1 = 9 it would need 9 = 3 \cdot 2, which is false. A second solution, not a multiple of r^n, is needed.

The second solution

Claim. If r is a double root, then t_n = n\,r^n is a solution.

Proof. Let n \ge 2. Using c_1 = 2r and c_2 = -r^2,

\square

Both facts about the double root were used: c_2 = -r^2 makes every term a multiple of r^n, and the 2 in c_1 = 2r makes 2(n-1) - (n-2) come out to exactly n. For a root that is not double, n\,r^n is not a solution (Exercise 13).

The theorem

By the combination fact of Solving and checking a two-term recurrence, Ar^n + Bnr^n = (A + Bn)r^n is a solution for any constants A and B.

Theorem (double root). Suppose the characteristic equation of a_n = c_1 a_{n-1} + c_2 a_{n-2}, with c_2 \ne 0, has a double root r. Then for every solution (a_n) there is exactly one pair of constants A, B with

Proof. Let (a_n) be a solution. Any pair that works must fit n = 0 and n = 1:

Since r \ne 0, these force A = a_0 and \displaystyle B = \frac{a_1}{r} - a_0, so at most one pair works. Let b_n = (A + Bn)r^n with this pair. Then (b_n) is a solution, and b_0 = a_0, b_1 = a_1. We prove a_n = b_n for every n \ge 0 by Strong induction and well-ordering. The cases n = 0 and n = 1 hold. Let n \ge 2 and assume a_k = b_k for every k < n. Both sequences obey the rule, so

Hence a_n = b_n for every n \ge 0. \square

This is the distinct-roots proof with n\,r^n in place of the second power. Only the two equations for A and B changed, and they can be solved because r \ne 0. A formula found any other way is checked exactly as in Solving and checking a two-term recurrence: two base cases and the identity f(n) = c_1 f(n-1) + c_2 f(n-2), then strong induction.

Why the factor n appears (intuition, not proof)

Picture a nearby rule whose roots r and s are different but close. By the distinct-roots theorem, \displaystyle \frac{1}{s - r}s^n - \frac{1}{s - r}r^n solves that rule, and for n \ge 1

The right side has n terms, each tending to r^{n-1} as s approaches r, so this solution tends to n\,r^{n-1}, and r times it to n\,r^n. As the two roots merge, r^n and s^n become the same solution, but their difference quotient survives as a new one. This is a picture, not a proof: a limit of solutions of other rules is not automatically a solution of this one. The substitution above is the proof. Exercises 7 and 10 put numbers on the picture.

Rules that look back three places

For a_n = c_1 a_{n-1} + c_2 a_{n-2} + c_3 a_{n-3} the characteristic equation is the cubic x^3 - c_1 x^2 - c_2 x - c_3 = 0. If it is (x - r)^3 = 0, a triple root, then every solution has the form

with A, B, C fixed by three starting values. This is stated here without proof. The pattern continues: a root repeated m times brings r^n, n\,r^n, \dots, n^{m-1}r^n.

Worked examples

Boundaries

• A double root only. The form (A + Bn)r^n is for c_1^2 + 4c_2 = 0. With two different roots n\,r^n is not a solution (Exercise 13), and the distinct-roots theorem applies.
• c_2 \ne 0. It makes r \ne 0, which the proof needs to find B. If c_2 = 0 the rule looks back only one place.
• Real coefficients give a real double root, namely \displaystyle \frac{c_1}{2}. Complex roots of a real quadratic always come as two different roots.
• No added term. A rule such as a_n = 2r\,a_{n-1} - r^2 a_{n-2} + d is not homogeneous, and this lesson does not treat it. Example 4 removed an added term only because that term was itself geometric.
• Three places back a triple root brings (A + Bn + Cn^2)r^n, stated here without proof.

Where this goes next

This finishes the two-term rules with constant coefficients: the characteristic equation has two different roots or one double root, and each case now has its theorem. The same pattern returns in differential equations, where y'' - 2ry' + r^2 y = 0 is solved by e^{rx} and x\,e^{rx}, with the same merging-roots picture behind it. In linear algebra, the matrix that steps (a_{n-1}, a_n) to (a_n, a_{n+1}) has a repeated eigenvalue but cannot be diagonalized, and the factor n comes out of its powers. The ratio argument of Exercise 14 is another use of Convergence of sequences.

Exercises

Solving with a double root

1. Solve a_n = 10a_{n-1} - 25a_{n-2} with a_0 = 3 and a_1 = 20.
2. Solve a_n = 14a_{n-1} - 49a_{n-2} with a_0 = 0 and a_1 = 7.
3. Solve a_n = -6a_{n-1} - 9a_{n-2} with a_0 = 1 and a_1 = 0.
4. Solve 9a_n = 6a_{n-1} - a_{n-2} with a_0 = 2 and a_1 = 2, and show that a_n approaches 0.
5. A sequence has a_1 = 12, a_2 = 108 and a_n = 12a_{n-1} - 36a_{n-2} for n \ge 3. Find a closed formula valid for n \ge 1.
6. Solve a_n = -12a_{n-1} - 36a_{n-2} with a_0 = -2 and a_1 = 6, and describe the signs of the terms.

Settings, limits and three places back

7. Change Example 4 so that Fennimore’s deposits rise 3\% a year while the account still pays 5\%: the deposit in year n is 2000(1.03)^n, and b_0 = 2000. Find a two-term rule for b_n, its characteristic roots, and a closed formula.
8. For which numbers c does a_n = c\,a_{n-1} - 81a_{n-2} have a double characteristic root? Give the root in each case.
9. The rule a_n = 9a_{n-1} - 27a_{n-2} + 27a_{n-3} has characteristic equation (x - 3)^3 = 0. Using the form stated for a triple root, solve it with a_0 = 1, a_1 = 6 and a_2 = 45, and check a_3 against the rule.
10. Compute \displaystyle \frac{s^4 - 3^4}{s - 3} for s = 3.1 and for s = 3.01, and compare with 4 \cdot 3^3.

Reasoning

11. A sequence has a_0 = 2, a_1 = 6 and 4a_n = 12a_{n-1} - 9a_{n-2} for n \ge 2. Prove by induction, without solving, that \displaystyle a_n = \frac{(n + 1)\,3^n}{2^{n-1}} for every n \ge 0.
12. Show that n^2\,5^n does not obey a_n = 10a_{n-1} - 25a_{n-2}, although 5^n and n\,5^n do.
13. Let r \ne 0. Prove that n\,r^n obeys a_n = c_1 a_{n-1} + c_2 a_{n-2} only if c_1 = 2r and c_2 = -r^2, that is, only if r is a double root.
14. Let a_n = (A + Bn)r^n with r \ne 0 and B \ne 0. Prove that a_{n+1}/a_n approaches r.
15. Let r be a double root and d_n = a_n - r\,a_{n-1} for n \ge 1. Show that d_n = r\,d_{n-1} for n \ge 2, and deduce that a_n / r^n is an arithmetic sequence. This is a second proof of the theorem.