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

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

Answer 2

`\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`