Question

Recall from class that we found that the Fibonacci sequence, with $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n - 2} + F_{n - 1}$, had a closed form $F_n = \frac{1}{\sqrt{5}} \left( \phi^n - \widehat{\phi}^n \right),$ where $\phi = \frac{1 + \sqrt{5}}{2} \; \text{and} \; \widehat{\phi} = \frac{1 - \sqrt{5}}{2}.$

The Lucas numbers are defined in the same way, but with different starting values. Let $L_0$ be the zeroth Lucas number and $L_1$ be the first. If
\begin{align*}
L_0 &= 2 \\
L_1 &= 1 \\
L_n &= L_{n - 1} + L_{n - 2} \; \text{for}\; n \geq 2
\end{align*}
then what is the tenth Lucas number? (Note: We seek a numerical answer.)

Answer 1

$\begin{bmatrix}L_n\\L_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}L_{n-1}\\L_{n-2}\end{bmatrix}$
$\begin{bmatrix}L_n\\L_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^2\begin{bmatrix}L_{n-2}\\L_{n-3}\end{bmatrix}$
$\begin{bmatrix}L_n\\L_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^3\begin{bmatrix}L_{n-3}\\L_{n-4}\end{bmatrix}$
$\vdots$
$\begin{bmatrix}L_n\\L_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}L_1\\L_0\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}1\\2\end{bmatrix}$

The easiest way to find an integer power of a matrix is to diagonalize the matrix first. If $\mathbf A=\begin{bmatrix}1&1\\1&0\end{bmatrix}=\mathbf{SD}\mathbf S^{-1}$ for some matrix $\mathbf S$ and diagonal matrix $\mathbf D$, then $\mathbf A^n=\mathbf{SD}^n\mathbf S^{-1}$.

You have

$\begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}\widehat\phi&\phi\\1&1\end{bmatrix}\begin{bmatrix}\widehat\phi&0\\0&\phi\end{bmatrix}\begin{bmatrix}\widehat\phi&\phi\\1&1\end{bmatrix}^{-1}$

which is a result you may have derived in class.

When $n=10$, you have

$\begin{bmatrix}L_{10}\\L_9\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^9\begin{bmatrix}1\\2\end{bmatrix}$
$\begin{bmatrix}L_{10}\\L_9\end{bmatrix}=\begin{bmatrix}\widehat\phi&\phi\\1&1\end{bmatrix}\begin{bmatrix}{\widehat\phi}^9&0\\0&\phi^9\end{bmatrix}\begin{bmatrix}\widehat\phi&\phi\\1&1\end{bmatrix}^{-1}\begin{bmatrix}1\\2\end{bmatrix}$
$\implies L_{10}=123$

Answer 2

Here is an easy way:

2+1=3

3+1=4

4+3=7

7+4=11

11+7=18

18+11=29

29+18=47

47+29=76

76+47=123