Click here to go back to the previous page
The fibonacci sequence! By employing matrix diagonalization in finding the nth fibonacci number, we can derive Binet's formula.
The fibonacci sequences starts as follows:
0, 1, 1, 2, 3, 5, 8, 13, ...
Let's start. We begin with a difference equation.
\[ F_{n} = F_{n-1} + F_{n-2} \]Turn this single equation into a system of two equations and two unknowns.
\[ F_{n} = F_{n-1} + F_{n-2} \qquad\qquad F_{n-1} = F_{n-1} \]We can use matrices to represent this system as
\[ \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} F_{n-1} = F_{n-1} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} \]The equation of interest is
\[ \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} \]First, we must generalize the equation. Let \(u_{n-1} = \begin{bmatrix} u_{n} \\ u_{n-1} \end{bmatrix}\) and \(\textbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\).
The equation above becomes
\[ u_{n-1} = \textbf{A}u_{n-2} \quad\Rightarrow\quad u_{n} = \textbf{A}u_{n-1} \]Now we have to figure out the starting point. We will define the two fibonacci numbers, \(F_{0}\) and \(F_{1}\), as 0 and 1 respectively.
Based on this
\[ u_{0} = \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \] \[ u_{1} = \textbf{A}u_{0} \qquad u_{2} = \textbf{A}u_{1} = \textbf{A}^{2}u_{0} \qquad \cdots \qquad u_{n} = \textbf{A}^{n}u_{0} \]We now have a general formula for the entire system. To determine its behavior as \(n\) gets larger and larger, we must find the eigenvalues of \(\textbf{A}\) and use diagonalization.
\[ \textbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \] \[ \det(\textbf{A} - \lambda\textbf{I}) = \det\left(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} - \lambda\textbf{I} \right) = \begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix} \] \[ \lambda^{2} - \lambda - 1 = 0 \]We can obtain the roots to this characteristic polynomial by either completing the square or using the quadratic formula.
\[ \lambda^{2} - \lambda - 1 + \frac{1}{4} = \frac{1}{4} \] \[ (\lambda - \frac{1}{2})^{2} - 1 = \frac{1}{4} \] \[ (\lambda - \frac{1}{2})^{2} = \frac{5}{4} \] \[ \lambda = \pm\sqrt{\frac{5}{4}} + \frac{1}{2} = \frac{1 \pm \sqrt{5}}{2}\]Therefore
\[ \lambda_{1} = \frac{1 + \sqrt{5}}{2} \qquad \lambda_{2} = \frac{1 - \sqrt{5}}{2} \]Wow! These two numbers are the golden ratio. When we calculate the eigenvectors, we will find that
\[ x_{1} = \begin{bmatrix} 1 + \sqrt{5} \\ 2 \end{bmatrix} \qquad x_{2} = \begin{bmatrix} 1 - \sqrt{5} \\ 2 \end{bmatrix} \]Now that we have all of this inforamtion, we know that the matrix of eigenvectors, \(\textbf{S}\), will be
\[ \textbf{S} = \begin{bmatrix} 1 + \sqrt{5} & 1 - \sqrt{5} \\ 2 & 2 \end{bmatrix} \]and the diagonal matrix of eigenvalues, \(\Lambda\), will be
\[ \Lambda = \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & 0 \\ 0 & \frac{1 - \sqrt{5}}{2} \end{bmatrix} \]Before we diagonalize \(\textbf{A}\), we need to find the inverse of \(\textbf{S}\). That should be pretty simple to do.
\[ \textbf{S}^{-1} = \frac{1}{\det\textbf{S}}\begin{bmatrix} s_{22} & -s_{12} \\ -s_{21} & s_{11} \end{bmatrix} = \frac{1}{4\sqrt{5}} \begin{bmatrix} 2 & \sqrt{5} - 1 \\ -2 & 1 + \sqrt{5} \end{bmatrix} \]Now if we diagonalize \(\textbf{A}\), it can be written as
\[ \textbf{A} = \textbf{S}\Lambda\textbf{S}^{-1} \]and the system now looks like this:
\[ u_{n} = \textbf{A}^{n}u_{0} = \textbf{S}\Lambda^{n}\textbf{S}^{-1}u_{0} \] \[ u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 + \sqrt{5} & 1 - \sqrt{5} \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & 0 \\ 0 & \frac{1 - \sqrt{5}}{2} \end{bmatrix}^{n} \frac{1}{4\sqrt{5}} \begin{bmatrix} 2 & \sqrt{5} - 1 \\ -2 & 1 + \sqrt{5} \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \]With this, we can work to simplify.
\[ u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 + \sqrt{5} & 1 - \sqrt{5} \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \left(\frac{1 + \sqrt{5}}{2}\right)^{n} & 0 \\ 0 & \left(\frac{1 - \sqrt{5}}{2}\right)^{n} \end{bmatrix} \frac{1}{4\sqrt{5}} \begin{bmatrix} 2 \\ -2 \end{bmatrix} \] \[ u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} (1 + \sqrt{5})\left(\frac{1 + \sqrt{5}}{2}\right)^{n} & (1 - \sqrt{5})\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \\ 2\left(\frac{1 + \sqrt{5}}{2}\right)^{n} & 2\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \end{bmatrix} \frac{1}{2\sqrt{5}} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \] \[ u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \frac{1}{2\sqrt{5}}\begin{bmatrix} (1 + \sqrt{5})\left(\frac{1 + \sqrt{5}}{2}\right)^{n} \\ 2\left(\frac{1 + \sqrt{5}}{2}\right)^{n} \end{bmatrix} - \frac{1}{2\sqrt{5}}\begin{bmatrix} (1 - \sqrt{5})\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \\ 2\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \end{bmatrix} \]We are only interesting in the second row of the solution because it gives us the formula for the nth fibobacci number. It tells us
\[ F_{n} = \left(\frac{1}{2\sqrt{5}}\right) 2\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1}{2\sqrt{5}}\right) 2\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \] \[ F_{n} = \left(\frac{1}{\sqrt{5}}\right) \left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1}{\sqrt{5}}\right) \left(\frac{1 - \sqrt{5}}{2}\right)^{n} \] \[ F_{n} = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}}{\sqrt{5}} \]And finally, we have arrived at Binet's formula.