The Fibonacci sequence is a sequence of integers defined recursively by
\begin{align*}
a_0&=0
&
a_1&=1
&
a_{n+1}&=a_n+a_{n-1},\quad n\geq 1\text{.}
\end{align*}
So the initial portion of the sequence is \(0,\,1,\,1,\,2,\,3,\,5,\,8,\,13,\,21,\,\ldots\text{.}\) In this subsection we will illustrate an application of eigenvalues and diagonalization through the determination of a closed-form expression for an arbitrary term of this sequence.
To begin, verify that for any \(n\geq 1\) the recursive statement above establishes the truth of the statement
\begin{align*}
\colvector{a_n\\a_{n+1}}
&=
\begin{bmatrix}0&1\\1&1\end{bmatrix}
\colvector{a_{n-1}\\a_n}\text{.}
\end{align*}
Let \(A\) denote this \(2\times 2\) matrix. Through repeated applications of the statement above we have
\begin{align*}
\colvector{a_n\\a_{n+1}}
&
=A\colvector{a_{n-1}\\a_n}
=A^2\colvector{a_{n-2}\\a_{n-1}}
=A^3\colvector{a_{n-3}\\a_{n-2}}
=\cdots
=A^n\colvector{a_{0}\\a_{1}}\text{.}
\end{align*}
In preparation for working with this high power of
\(A\text{,}\) not unlike in
Example HPDM, we will diagonalize
\(A\text{.}\) The two distinct eigenvalues of
\(A\) arise as roots of the polynomial
\(x^2-x-1\text{,}\) and are
\begin{align*}
\rho&=\frac{1+\sqrt{5}}{2}
&
\delta&=\frac{1-\sqrt{5}}{2}\text{.}
\end{align*}
With two distinct eigenvalues,
Theorem DED implies that
\(A\) is diagonalizable. It will be easier to compute with these eigenvalues once you confirm the following properties (all but the last can be derived from the fact that
\(\rho\) and
\(\delta\) are roots of the polynomial, in a factored or unfactored form)
\begin{align*}
\rho+\delta&=1
&
\rho\delta&=-1
&
1+\rho&=\rho^2
&
1+\delta&=\delta^2
&
\rho-\delta&=\sqrt{5}\text{.}
\end{align*}
Then eigenvectors of \(A\) (for \(\rho\) and \(\delta\text{,}\) respectively) are
\begin{align*}
&\colvector{1\\\rho}
&
&\colvector{1\\\delta}
\end{align*}
which can be easily confirmed, as we demonstrate for the eigenvector for \(\rho\text{,}\)
\begin{align*}
\begin{bmatrix}0&1\\1&1\end{bmatrix}\colvector{1\\\rho}
&
=\colvector{\rho\\1+\rho}
=\colvector{\rho\\\rho^2}
=\rho\colvector{1\\\rho}\text{.}
\end{align*}
From the proof of
Theorem DC we know
\(A\) can be diagonalized by a matrix
\(S\) with these eigenvectors as columns, giving
\(D=\inverse{S}AS\text{.}\) We list
\(S\text{,}\) \(\inverse{S}\) and the diagonal matrix
\(D\text{,}\)
\begin{align*}
S&=\begin{bmatrix}1&1\\\rho&\delta\end{bmatrix}
&
\inverse{S}&=\frac{1}{\rho-\delta}\begin{bmatrix}-\delta&1\\\rho&-1\end{bmatrix}
&
D&=\begin{bmatrix}\rho&0\\0&\delta\end{bmatrix}\text{.}
\end{align*}
OK, we have everything in place now. The main step in the following is to replace \(A\) by \(SD\inverse{S}\text{.}\) Here we go,
\begin{align*}
\colvector{a_n\\a_{n+1}}
&=A^n\colvector{a_{0}\\a_{1}}\\
&=\left(SD\inverse{S}\right)^n\colvector{a_{0}\\a_{1}}\\
&=SD\inverse{S}SD\inverse{S}SD\inverse{S}\cdots SD\inverse{S}\colvector{a_{0}\\a_{1}}\\
&=SDDD\cdots D\inverse{S}\colvector{a_{0}\\a_{1}}\\
&=SD^n\inverse{S}\colvector{a_{0}\\a_{1}}\\
&=
\begin{bmatrix}1&1\\\rho&\delta\end{bmatrix}
\begin{bmatrix}\rho&0\\0&\delta\end{bmatrix}^n
\frac{1}{\rho-\delta}\begin{bmatrix}-\delta&1\\\rho&-1\end{bmatrix}
\colvector{a_{0}\\a_{1}}\\
&=
\frac{1}{\rho-\delta}
\begin{bmatrix}1&1\\\rho&\delta\end{bmatrix}
\begin{bmatrix}\rho^n&0\\0&\delta^n\end{bmatrix}
\begin{bmatrix}-\delta&1\\\rho&-1\end{bmatrix}
\colvector{0\\1}\\
&=
\frac{1}{\rho-\delta}
\begin{bmatrix}1&1\\\rho&\delta\end{bmatrix}
\begin{bmatrix}\rho^n&0\\0&\delta^n\end{bmatrix}
\colvector{1\\-1}\\
&=
\frac{1}{\rho-\delta}
\begin{bmatrix}1&1\\\rho&\delta\end{bmatrix}
\colvector{\rho^n\\-\delta^n}\\
&=
\frac{1}{\rho-\delta}
\colvector{\rho^n-\delta^n\\\rho^{n+1}-\delta^{n+1}}\text{.}
\end{align*}
Performing the scalar multiplication and equating the first entries of the two vectors, we arrive at the closed form expression
\begin{align*}
a_n&=\frac{1}{\rho-\delta}\left(\rho^n-\delta^n\right)\\
&=\frac{1}{\sqrt{5}}
\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\\
&=\frac{1}{2^n\sqrt{5}}
\left(\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right)\text{.}
\end{align*}
Notice that it does not matter whether we use the equality of the first or second entries of the vectors, we will arrive at the same formula, once in terms of \(n\) and again in terms of \(n+1\text{.}\) Also, our definition clearly describes a sequence that will only contain integers, yet the presence of the irrational number \(\sqrt{5}\) might make us suspicious. But no, our expression for \(a^n\) will always yield an integer!
The Fibonacci sequence, and generalizations of it, have been extensively studied (Fibonacci lived in the 12th and 13th centuries). There are many ways to derive the closed-form expression we just found, and our approach may not be the most efficient route. But it is a nice demonstration of how diagonalization can be used to solve a problem outside the field of linear algebra.
