### Key Concepts

 Data Analytics: Application of Linear Algebra - Fibonacci Sequence
Written by FemiByte
Thursday, 14 February 2013 05:30

## Application of Linear Algebra - Fibonacci sequence

The Fibonacci sequence is defined as : $f_{n+1} = f_n + f_{n-1},\text{ }f_0=0, f_1=1$ Thus for $n=2$, we have $f_2 = f_1 + f_0$ We can write the above equation in matrix form as follows: $\left[ \begin{array}{c}f_2\\f_1\end{array}\right]= \left[ \begin{array}{cc}1&1\\1&0\end{array}\right] \left[ \begin{array}{c}f_1\\f_0\end{array}\right]$ Let us refer to the matrix $\left[ \begin{array}{cc}1&1\\1&0\end{array}\right]$ as $A$.
If we iterate using the above matrix equation, we discover that we can obtain an expression for $f_n$ by multiplying by $A$ $n$ times: $\left[ \begin{array}{c}f_{n+1}\\f_n\end{array}\right]=\left[\begin{array}{cc}1&1\\1&0\end{array}\right]^n \left[ \begin{array}{c}f_1\\f_0\end{array}\right]$

The question then becomes how we can use the iterative relation move to arrive at a closed form expression for $f_n$. Putting on our Linear Algebra hat, we recognize that we can obtain an expression for the $n-th$ power of $A$ if $A$ is diagonalizable. To do that, let us obtain the eigenvalue from the well-known equation : $\text{det(}A-\lambda I \text{)}=0$, i.e. $(1-\lambda)(0-\lambda)-1=0$ which produces
$\lambda^2-\lambda-1=0$. Solving this equation, we obtain the following 2 eigenvalues:
$\lambda_1=\frac{1+\sqrt{5}}{2}, \lambda_2=\frac{1-\sqrt{5}}{2}$
Since the eigenvalues are different, we conclude that $A$ is diagonalizable and can be written as
$AS=S \Lambda \text{ } => A = S \Lambda S^{-1}$
where $S$ is the matrix of eigenvectors.

From that we can show that $A^n = S \Lambda^n S^{-1}$ 1
The eigenvectors can be found by solving
$\left[\begin{array}{cc}1-\lambda_1&&1\\1&&-\lambda_1\end{array}\right]\left[\begin{array}{c}x_1\\y_1\end{array}\right]=\left[\begin{array}{c}0\\0\end{array}\right]$
and
$\left[\begin{array}{cc}1-\lambda_2&&1\\1&&-\lambda_2\end{array}\right]\left[\begin{array}{c}x_2\\y_2\end{array}\right]=\left[\begin{array}{c}0\\0\end{array}\right]$
which produce the following eigenvalue/eigenvector pairs:
$\lambda_1=\frac{1+\sqrt{5}}{2}, \text{ } e_1=\left[\begin{array}{c}\frac{1+\sqrt{5}}{2}\\1\end{array}\right]$
and
$\lambda_2=\frac{1-\sqrt{5}}{2}, \text{ } e_2=\left[\begin{array}{c}\frac{1-\sqrt{5}}{2}\\1\end{array}\right]$

We can then write $S$ as
$S=\left[\begin{array}{cc}\lambda_1&&\lambda_2\\1&&1\end{array}\right] = \left[\begin{array}{cc}\frac{1+\sqrt{5}}{2}&&\frac{1-\sqrt{5}}{2}\\1&&1\end{array}\right]$
and $\Lambda$ as
$\Lambda=\left[\begin{array}{cc}\lambda_1&&0\\0&&\lambda_2\end{array}\right] = \left[\begin{array}{cc}\frac{1+\sqrt{5}}{2}&&0\\0&&\frac{1-\sqrt{5}}{2}\end{array}\right]$

What's left for us now is to calculate $S^{-1}$.
For a $2x2$ matrix:
$M=\left[\begin{array}{cc}a&&b\\c&&d\end{array}\right] => M^{-1}=\frac{1}{ad-bc}\left[\begin{array}{cc}d&&-b\\-c&&a\end{array}\right]$
In this case
$S^{-1}=\frac{1}{\sqrt{5}}\left[\begin{array}{cc}1&&-\frac{1-\sqrt{5}}{2}\\-1&&\frac{1+\sqrt{5}}{2}\end{array}\right]$
We can now substitute in the expression to obtain : $A^n=S\Lambda^n S^{-1}$:
$\frac{1}{\lambda_1-\lambda_2} \left[\begin{array}{cc}\lambda_1^{n+1}-\lambda_2^{n+1}&&\lambda_1^n-\lambda_2^n\\\lambda_1^n-\lambda_2^n&&\lambda_1^{n-1}-\lambda_2^{n-1}\end{array}\right]$

Hence $\left[ \begin{array}{c}f_{n+1}\\f_n\end{array}\right]= \frac{1}{\lambda_1-\lambda_2} \left[\begin{array}{cc}\lambda_1^{n+1}-\lambda_2^{n+1}&&\lambda_1^n-\lambda_2^n\\\lambda_1^n-\lambda_2^n&&\lambda_1^{n-1}-\lambda_2^{n-1}\end{array}\right]\left[ \begin{array}{c}f_1\\f_0\end{array}\right]$
We can then see that $f_n$ is given by
$f_n=\frac{1}{\lambda_1-\lambda_2}\left(\lambda_1^n-\lambda_2^n\right)= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$since $f_1=1,f_0=0$

The above is our closed form expression for $f_n$.

1. Given that $A = S \Lambda S^{-1}$, we obtain $A^2 = S \Lambda S^{-1} S \Lambda S^{-1} = S \Lambda^2 S^{-1}$ since $S^{-1}S$ cancel each other out. Continuing this process until we reach $n$, we can see that $A^n = S \Lambda^n S^{-1}$

Last Updated on Saturday, 16 February 2013 08:17