Guess rⁿ
Tonight's idea
Take the rule \(a_n = a_{n-1} + 6a_{n-2}\), a linear recurrence. Starting from \(a_0 = 1\), \(a_1 = 8\) it gives 1, 8, 14, 62, 146, 518, … To reach the 100th term you seem to need the 99 before it. You do not.
Guess that a power works: \(a_n = r^n\). The rule becomes \(r^n = r^{n-1} + 6r^{n-2}\). Divide by \(r^{n-2}\):
\[r^2 = r + 6, \quad\text{so}\quad r = 3 \ \text{or}\ r = -2.\]
So \(3^n\) obeys the rule, and so does \((-2)^n\). Neither starts 1, 8. But the rule only adds and scales, so any mixture \(A \cdot 3^n + B \cdot (-2)^n\) obeys it too. Choose \(A\) and \(B\) to fit the start. \(n = 0\) gives \(A + B = 1\), and \(n = 1\) gives \(3A - 2B = 8\). So \(A = 2\), \(B = -1\).
\(a_n = 2 \cdot 3^n - (-2)^n\). Check: \(a_3 = 54 + 8 = 62\).
The mixture fits the first two terms and obeys the rule, so it fits every term. This always works when the quadratic has two different roots.
Watch one: a formula for Fibonacci
The Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, … obey \(F_n = F_{n-1} + F_{n-2}\) with \(F_0 = 0\), \(F_1 = 1\). Guessing \(r^n\) gives \(r^2 = r + 1\), with roots \(\varphi = \tfrac{1 + \sqrt5}{2} \approx 1.618\) and \(\psi = \tfrac{1 - \sqrt5}{2} \approx -0.618\). Fit the start: \(A + B = 0\) and \(A\varphi + B\psi = 1\). So \(B = -A\) and \(A(\varphi - \psi) = A\sqrt5 = 1\).
\[F_n = \frac{\varphi^n - \psi^n}{\sqrt5}.\]
Whole numbers, from a formula full of \(\sqrt5\). Since \(\psi^n\) shrinks towards 0, \(F_n\) is the whole number nearest \(\varphi^n/\sqrt5\): for \(n = 10\) that is \(55.004\), and \(F_{10} = 55\).
Next year roots like 3 and \(-2\) come back as the eigenvalues of a matrix: The directions a matrix leaves alone.
Your turn
- \(a_n = 5a_{n-1} - 6a_{n-2}\) with \(a_0 = 0\), \(a_1 = 1\). Find a formula for \(a_n\). Check it against \(a_3\) worked out from the rule.
- \(a_n = 2a_{n-1} + 3a_{n-2}\) with \(a_0 = 3\), \(a_1 = 1\). Find a formula for \(a_n\), and use it to find \(a_{10}\).
- The Lucas numbers obey the Fibonacci rule but start \(L_0 = 2\), \(L_1 = 1\). Find a formula for \(L_n\) in terms of \(\varphi\) and \(\psi\). Use a calculator and the size of \(\psi\) to find \(L_{10}\) without working out the terms before it.
- A sequence has the formula \(a_n = 2^n + 5^n\). Find a rule \(a_n = p\,a_{n-1} + q\,a_{n-2}\) that it obeys, and its two starting values. What does the ratio \(a_{n+1}/a_n\) approach as \(n\) grows, and why?
Stretch: when the roots collide
For \(a_n = 4a_{n-1} - 4a_{n-2}\) the quadratic has only one root, \(r = 2\). Show that \(n \cdot 2^n\) also obeys the rule. Then find the formula when \(a_0 = 1\), \(a_1 = 4\).
Answers
- \(r^2 = 5r - 6\) gives \(r = 2\) or \(3\). \(A + B = 0\) and \(2A + 3B = 1\), so \(B = 1\), \(A = -1\): \(a_n = 3^n - 2^n\). The rule gives 0, 1, 5, 19, and \(3^3 - 2^3 = 19\).
- \(r^2 = 2r + 3\) gives \(r = 3\) or \(-1\). \(A + B = 3\) and \(3A - B = 1\), so \(A = 1\), \(B = 2\): \(a_n = 3^n + 2(-1)^n\). Then \(a_{10} = 59049 + 2 = 59051\).
- \(A + B = 2\) and \(A\varphi + B\psi = 1\). Since \(\varphi + \psi = 1\), \(A = B = 1\) works: \(L_n = \varphi^n + \psi^n\). \(\psi^{10} \approx 0.008\) is tiny, so \(L_{10}\) is the whole number nearest \(\varphi^{10} \approx 122.99\), which is 123. (The sequence runs 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123.)
- The roots must be 2 and 5: \((r - 2)(r - 5) = r^2 - 7r + 10\), so \(r^2 = 7r - 10\) and \(a_n = 7a_{n-1} - 10a_{n-2}\), with \(a_0 = 2\), \(a_1 = 7\). Check: \(7 \times 7 - 10 \times 2 = 29 = 4 + 25\). The ratio approaches 5. The larger root wins: \(5^n\) soon dwarfs \(2^n\).
Stretch. Put \(a_n = n \cdot 2^n\) into the right side: \(4(n-1)2^{n-1} - 4(n-2)2^{n-2} = 2^n\big(2(n-1) - (n-2)\big) = n \cdot 2^n\). So try \(a_n = (A + Bn)2^n\). \(a_0 = 1\) gives \(A = 1\); \(a_1 = 4\) gives \(2(1 + B) = 4\), \(B = 1\). So \(a_n = (n + 1)2^n\): 1, 4, 12, 32, 80, …