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.