Home Features Data Analytics Data Analytics: Application of Linear Algebra - Fibonacci Sequence
Data Analytics: Application of Linear Algebra - Fibonacci Sequence PDF Print E-mail
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
 

joomla 1.5 stats