Solving and checking a two-term recurrence

When you reach for it

A rule of the form

with fixed numbers c_1 and c_2 \ne 0 and two starting values a_0, a_1, fixes every term, but only one at a time. Reach for this move when you want a_n straight from n: a far term, the rate of growth, or a fact about every term at once. Closed form versus recursive form turned one-term rules into formulas by spotting a pattern; a rule that looks back two places shows no pattern, yet its answer is still built from powers. The same method gives the closed formula for the Fibonacci numbers of The Fibonacci sequence, with the golden ratio in it. A second move belongs here too: checking a closed formula against the rule by Strong induction and well-ordering proves it for every n, however the formula was found.

Such a rule is a linear homogeneous recurrence of order two with constant coefficients: earlier terms are only multiplied by constants and added, nothing else is added, and it looks back two places. A solution is any sequence that obeys the rule for every n \ge 2, whatever its starting values.

The procedure

Day 1: trying a power

A geometric sequence obeys a one-term rule, so try one in the two-term rule. For r \ne 0, the sequence r^n is a solution exactly when

Dividing by r^{n-2}, which is not zero, turns every one of these equations into the same quadratic,

and multiplying by r^{n-2} reverses the step. This quadratic is the characteristic equation of the rule, and its roots are the characteristic roots. So r^n is a solution exactly when r is a characteristic root. The product of the roots is -c_2 \ne 0, so neither root is 0. The roots come from factoring or from the The quadratic formula.

Solutions also combine. If (s_n) and (t_n) are solutions and A, B are constants, then for n \ge 2, by the distributive property and regrouping,

so (As_n + Bt_n) is a solution too. Two roots therefore give a family Ar_1^n + Br_2^n, and the theorem says the family holds every solution.

Theorem (distinct roots). Suppose the characteristic equation of a_n = c_1 a_{n-1} + c_2 a_{n-2} has two different roots r_1 and r_2. 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 A, B that works must fit n = 0 and n = 1:

Subtracting r_1 times the first equation from the second leaves B(r_2 - r_1) = a_1 - r_1 a_0. Since r_2 - r_1 \ne 0,

So at most one pair works. Let b_n = A r_1^n + B r_2^n with this pair. By the two facts above (b_n) is a solution, and b_0 = a_0, b_1 = a_1 by the choice of A and B. We prove a_n = b_n for every n \ge 0 by strong induction. 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

So for a given rule: find the roots, write Ar_1^n + Br_2^n, and fix A and B from the two starting values.

Day 1: checking a closed form by induction

The induction at the end of that proof works for any formula f(n) proposed for the sequence with rule a_n = c_1 a_{n-1} + c_2 a_{n-2} and starting values a_0, a_1. Two things settle it:

• the base cases f(0) = a_0 and f(1) = a_1;
• the identity f(n) = c_1 f(n-1) + c_2 f(n-2) for every n \ge 2, which is algebra.

Then if a_k = f(k) for all k < n, we get a_n = c_1 f(n-1) + c_2 f(n-2) = f(n), and strong induction gives a_n = f(n) for every n \ge 0. Both base cases are needed, because a formula can obey the rule and still be a different solution (Example 2). This is the two-base-case induction of How induction works: base case, hypothesis and step and Strong induction and well-ordering.

Day 1: rules that look back one place

A rule a_n = c\,a_{n-1} + d with c \ne 1 adds a constant at each step, so it is not geometric. Shift it. A constant sequence p obeys the rule when p = cp + d, that is, \displaystyle p = \frac{d}{1 - c}. Subtracting p = cp + d from a_n = c\,a_{n-1} + d gives

so a_n - p is geometric with ratio c (Geometric sequences and the explicit formula), and

When c = 1 the rule is arithmetic and a_n = a_0 + nd.

Day 2: the Fibonacci numbers and the golden ratio

With F_0 = 0, F_1 = 1 and F_n = F_{n-1} + F_{n-2}, the characteristic equation is r^2 = r + 1. The quadratic formula gives two different roots,

The number \varphi is the golden ratio. Three facts do most of the work: \varphi + \psi = 1, \varphi\psi = -1 and \displaystyle \varphi - \psi = \sqrt{5}. Example 4 finds Binet’s formula,

Because |\psi| < 1, the term \psi^n shrinks toward 0. So F_n is the integer nearest to \displaystyle \varphi^n/\sqrt{5}, and the ratios F_{n+1}/F_n approach \varphi (Example 5).

Day 2: negative and irrational roots

The theorem asks only that the roots be different, not positive or rational. A negative root r makes r^n change sign at every step; when it is the root of larger size, the terms eventually alternate in sign (Example 6). Irrational roots such as \displaystyle 1 \pm \sqrt{3} come as a pair \displaystyle u \pm \sqrt{w} when c_1 and c_2 are rational, and with rational starting values the square roots cancel in every term (Example 7). If |r_1| > |r_2| and A \ne 0, the term Ar_1^n takes over and a_{n+1}/a_n approaches r_1 (Exercise 20).

Worked examples

Boundaries

• Constant coefficients. Rules such as a_n = n\,a_{n-1} or a_n = a_{n-1}^2 are not of this kind, and powers do not solve them. A rule looking back k places works the same way with a characteristic equation of degree k, stated here without proof.
• c_2 \ne 0. Otherwise 0 is a root and the rule looks back only one place.
• Different roots. For a double root r, the family Ar^n + Br^n = (A + B)r^n has one free constant and cannot match every pair of starting values; see Two-term recurrences with a repeated root.
• Real roots here. When c_1^2 + 4c_2 < 0 the roots are complex. The theorem still holds with complex A and B, but that is not pursued here (Exercise 21).
• Homogeneous rules. An added constant needs the shift of Day 1, which needs c \ne 1. For a_n = c_1 a_{n-1} + c_2 a_{n-2} + d the shift \displaystyle p = \frac{d}{1 - c_1 - c_2} works when 1 is not a characteristic root (Exercise 12).
• Rounding needs a small second term, \displaystyle |Br_2^n| < \frac{1}{2}, as for F_n and g_n.
• The ratio limit needs A \ne 0. The rule of Example 1 with a_0 = 2, a_1 = 4 gives a_n = 2^{n+1}, whose ratios are 2, not the larger root 3.

Where this goes next

Two-term recurrences with a repeated root finishes the two-term case: a double root r brings in nr^n beside r^n. Setting up a recurrence from a counting problem supplies rules to solve. The ratio limits of Example 5 and Exercise 20 rest on Convergence of sequences. The idea of trying an exponential and getting a polynomial returns in differential equations with constant coefficients, and in linear algebra, where the step from (a_{n-1}, a_n) to (a_n, a_{n+1}) is a matrix whose eigenvalues are the characteristic roots.

Exercises

Day 1: two different roots

1. Solve a_n = 7a_{n-1} - 12a_{n-2} with a_0 = 3 and a_1 = 10.
2. Solve a_n = 6a_{n-1} - 5a_{n-2} with a_0 = 0 and a_1 = 8.
3. Solve a_n = 9a_{n-1} - 20a_{n-2} with a_0 = 1 and a_1 = 3, and find the first negative term.
4. Solve 9a_n = 9a_{n-1} - 2a_{n-2} with a_0 = 2 and a_1 = 1.
5. A sequence has a_1 = 1, a_2 = 11 and a_n = 8a_{n-1} - 15a_{n-2} for n \ge 3. Find a closed formula valid for n \ge 1.

Day 1: checking formulas and shifting

6. A sequence has a_0 = 0, a_1 = 4 and a_n = 8a_{n-1} - 12a_{n-2} for n \ge 2. Prove by induction, without solving, that a_n = 6^n - 2^n for every n \ge 0.
7. A sequence has a_0 = 1, a_1 = 2 and a_n = 4a_{n-1} - 3a_{n-2} for n \ge 2. Its first three terms fit n^2 + 1. Show that the fit fails at n = 3, then find the correct closed formula and prove it by induction.
8. Solve a_n = 5a_{n-1} - 8 with a_0 = 1.
9. Solve \displaystyle a_n = \frac{1}{3}a_{n-1} + 8 with a_0 = 30, and say what the terms approach.
10. Mirza’s savings account starts with \$1000. At the end of each month it earns 2\% interest, and then he withdraws \$50. Write a rule for the balance b_n after n months, find a closed formula, and find the first month in which the full withdrawal cannot be made.

Day 1: reasoning

11. Show that the sequence 2^n + n (for n \ge 0) obeys no rule a_n = c_1 a_{n-1} + c_2 a_{n-2} with constants c_1 and c_2.
12. Let a_n = c_1 a_{n-1} + c_2 a_{n-2} + d with c_1 + c_2 \ne 1, and \displaystyle p = \frac{d}{1 - c_1 - c_2}. Prove that b_n = a_n - p obeys b_n = c_1 b_{n-1} + c_2 b_{n-2}, then solve a_n = 2a_{n-1} + 3a_{n-2} - 8 with a_0 = a_1 = 4.

Day 2: the golden ratio

13. Use \varphi^{15} \approx 1364.00073 to find F_{15}, and say how far \displaystyle \varphi^{15}/\sqrt{5} is from it.
14. A sequence has u_0 = 4, u_1 = 1 and the Fibonacci rule u_n = u_{n-1} + u_{n-2}. Find its closed formula in terms of \varphi and \psi, and the limit of u_{n+1}/u_n.
15. Prove that \varphi^n = F_n\varphi + F_{n-1} for every n \ge 1, and use it to write \varphi^6 in the form \displaystyle u + v\sqrt{5} with integers u and v.

Day 2: negative and irrational roots

16. Solve a_n = 2a_{n-1} + 15a_{n-2} with a_0 = 0 and a_1 = 8, and show that every term after a_0 is positive.
17. Solve a_n = -2a_{n-1} + 8a_{n-2} with a_0 = 1 and a_1 = -10, and prove that the terms alternate in sign.
18. Solve a_n = 4a_{n-1} - a_{n-2} with a_0 = 2 and a_1 = 4. Use the answer to find the integer nearest to \displaystyle (2 + \sqrt{3})^6 without a calculator.
19. In Setting up a recurrence from a counting problem, the tilings of a 2 by n board satisfy w_n = w_{n-1} + 2w_{n-2} with w_0 = w_1 = 1, and the formula \displaystyle w_n = \frac{2^{n+1} + (-1)^n}{3} was guessed and then proved. Derive it from the characteristic roots instead.

Day 2: reasoning

20. Let a_n = Ar_1^n + Br_2^n with real r_1, r_2, |r_1| > |r_2| and A \ne 0. Prove that a_{n+1}/a_n approaches r_1. What does this say about the strings of Example 7?
21. The rule a_n = a_{n-1} - a_{n-2} has characteristic equation r^2 - r + 1 = 0, which has no real roots. Prove that every solution repeats with period 6: a_{n+6} = a_n for every n \ge 0.