# Fibonacci Number

### Closed-form Expression:

So far, we’ve been using the Fibonacci recurrence to calculate $F_n$, but it turns out there’s also a nice closed form expression. We can use the matrix multiplication result from above to see this.

$$A = \left( \begin{array}{c c} 1 & 1 \\ 1 & 0 \\ \end{array} \right)$$

Essentially, we want to find a way to express the $n^{\text{th}}$ Fibonacci number without using matrices. One possible approach is to diagonalize $A$ and take the diagonal matrix to the $n^{\text{th}}$ power, which is considerably easier than doing $A^n$. Obviously, we need to find the eigenvalues and eigenvectors of the matrix $A$:

$$\begin{eqnarray} 0 & = & \det\left( \left( \begin{array}{c c} 1 & 1 \\ 1 & 0 \\ \end{array} \right) \left( \begin{array}{c c} \lambda & 0 \\ 0 & \lambda \\ \end{array} \right) \right) \\ & = & \det\left( \left( \begin{array}{c c} 1-\lambda & 1 \\ 1 & -\lambda \\ \end{array} \right) \right) \\ & = & -\lambda + \lambda^2 – 1 \\ \lambda & = & \frac{1 \pm \sqrt{5}}{2} \end{eqnarray}$$

Note that $\frac{1 + \sqrt{5}}{2}$ is the golden ratio, usually given as $\varphi$, and $\frac{1 – \sqrt{5}}{2}$ is $-\frac{1}{\varphi} = 1 – \varphi$. We now need to calculate the eigenvectors to determine the diagonalization matrix.

$$\begin{eqnarray} A \mid \mathbf{v_1} \rangle & = & \lambda_1 \mid \mathbf{v_1} \rangle \\ \left( \begin{array}{c c} 1 & 1 \\ 1 & 0 \\ \end{array} \right) \left[ \begin{array}{c} x_1 \\ x_2 \end{array} \right] & = & \varphi \left[ \begin{array}{c} x_1 \\ x_2 \end{array} \right] \\ \left[ \begin{array}{c} x_1 + x_2 \\ x_1 \end{array} \right] & = & \left[ \begin{array}{c} \varphi \; x_1 \\ \varphi \; x_2 \end{array} \right] \\ x_1 & = & \varphi x_2 \\ \mid \mathbf{v_1} \rangle & = & c \left[ \begin{matrix} \varphi \\ 1 \end{matrix} \right] \end{eqnarray}$$

The steps are very similar for $\mathbf{v_2}$:

$$\begin{eqnarray} x_1 & = & (1 – \varphi) x_2 \\ \mid \mathbf{v_2} \rangle & = & c \left[ \begin{matrix} 1-\varphi \\ 1 \end{matrix} \right] & = & c \left[ \begin{matrix} 1 \\ -\varphi \end{matrix} \right] \end{eqnarray}$$

The diagonalization matrix, $P$, of $A$ is the matrix formed by taking the eigenvectors of $A$ as the columns of $P$:

$$P = \left( \begin{array}{c c} \varphi & 1 \\ 1 & -\varphi \\ \end{array} \right)$$

And the diagonal matrix of $A$ is formed by placing eigenvalues along the diagonal of a $2 \times 2$ matrix (or calculated as $P^{-1} A P$):

$$D = \left( \begin{array}{c c} \varphi & 0 \\ 0 & -\frac{1}{\varphi} \\ \end{array} \right)$$

As I already stated, the nice thing about diagonal matrices is how easy it is to perform operations on it (just operate on each element).

$$\begin{eqnarray} A^n & = & P D^n P^{-1} \\ & = & \left( \begin{array}{c c} \varphi & 1 \\ 1 & -\varphi \\ \end{array} \right) \left( \begin{array}{c c} \varphi & 0 \\ 0 & -\frac{1}{\varphi} \\ \end{array} \right)^n \frac{1}{\varphi + 2} \left( \begin{array}{c c} \varphi & 1 \\ 1 & -\varphi \\ \end{array} \right) \\ & = & \frac{1}{\varphi + 2} \left( \begin{array}{c c} \varphi & 1 \\ 1 & -\varphi \\ \end{array} \right) \left( \begin{array}{c c} \varphi^n & 0 \\ 0 & \left(-\frac{1}{\varphi}\right)^n \\ \end{array} \right) \left( \begin{array}{c c} \varphi & 1 \\ 1 & -\varphi \\ \end{array} \right) \\ & = & \frac{1}{\varphi + 2} \left( \begin{array}{c c} \varphi^{n+1} & \left(-\frac{1}{\varphi}\right)^n \\ \varphi^n & \left(-\frac{1}{\varphi}\right)^{n-1} \\ \end{array} \right) \left( \begin{array}{c c} \varphi & 1 \\ 1 & -\varphi \\ \end{array} \right) \\ & = & \frac{1}{\varphi + 2} \left( \begin{array}{c c} \varphi^{n+2} + \left(-\frac{1}{\varphi}\right)^n & \varphi^{n+1} + \left(-\frac{1}{\varphi}\right)^{n-1} \\ \varphi^{n+1} + \left(-\frac{1}{\varphi}\right)^{n-1} & \varphi^n + \left(-\frac{1}{\varphi}\right)^{n-2} \\ \end{array} \right) \end{eqnarray}$$

With the closed form for the $n^{\text{th}}$ power of $A$, finding $F_n$ is fairly simple.

$$\begin{eqnarray} F_n & = & \frac{1}{\varphi + 2} \left(\varphi^{n+1} + \left(-\frac{1}{\varphi}\right)^{n-1}\right) \\ & = & \frac{1}{\varphi + 2} \left(\varphi \varphi^{n} -\varphi \left(-\frac{1}{\varphi}\right)^{n}\right) \\ & = & \frac{1+\sqrt{5}}{5+\sqrt{5}} \left(\varphi^{n} – \left(-\varphi\right)^{-n}\right) \\ & = & \frac{\varphi^{n} – \left(-\varphi\right)^{-n}}{\sqrt{5}} \\ \end{eqnarray}$$

This is probably the form most people are familiar with. Notice that it should supposedly give a fairly quick way of calculating $F_n$. However, practically, this formula isn’t useful for such a purpose, since $\varphi$ is an irrational number, and errors would accumulate pretty quickly. In some cases, this formula, known as Binet’s formula, can be useful for certain number theory applications.