Notes: Solve Fibonacci Sequence with Linear Algebra

Fibonacci Sequence

Fibonacci Sequence is a sequence defined recursively \[\left(x_0,x_1,\dots,x_n,\dots \right)\], Satisfying: \[ x_{n+2}=x_{n+1}+x_n \ where\ n\geq 0\]

Let \[V=\left\{\left(x_0,x_1,x_2,\dots,x_n,\dots\right)\dots\right\}\] be vector space of all such sequences

Claim: $V$ has dimension 2

\[a=\left( 0, 1, a_2, a_3, a_4, \dots\right)\ a_{n+2}=a_{n+1}+a_{n}\] \[b=\left( 1, 0, b_2, b_3, b_4, \dots\right)\ b_{n+2}=b_{n+1}+b_{n}\]

We show $\{a,b\}$ forms a basis $B$ of $V$.

It is obvious that $\{a,b\}$ are linearly independent. We want to show that $\{a,b\}$ spans $V$, that is $v \in V$ \[ v= c_1 a+c_2b\] \[ \begin{aligned} (x_0,x_1,x_2,\dots,x_n,\dots) & = c_1 ( 0,1,a_2,a_3,\dots)+c_2 (1,0,b_2,b_3,\dots)\\ & = (c_2,c_1,c_1a_2+c_2b_2,\dots,c_1a_n+c_2b_n) \end{aligned} \]

So

\[ \begin{aligned} a &= (0,1,1,2,3,5,8,\dots) \\ b &= (1,0,1,1,2,3,5,8,\dots) \end{aligned} \]

\[ x_n = x_0b_n + x_1a_n \] The above formula can be proved by induction.

Now define $E:V\to V$ advancing linear transfomration such that $E(x_0,x_1,x_2,\dots)=(x_1,x_2,x_3,\dots)

We want to find eigenvectors and eigenvalues of such linear transformation $Ev=\lambda v$

\begin{aligned} E=(x_0,x_1,x_2,\dots,x_n,\dots) &= \lambda (x_0,x_1,x_2,\dots,x_n,\dots) \\ (x_1,x_2,x_3,\dots,x_{n+1},\dots) &= (\lambda x_0, \lambda x_1, \lambda x_2,\dots, \lambda x_n, \dots) \end{aligned}

\begin{aligned} x_1 &= \lambda x_0 \\ x_2 &= \lambda x_1 = \lambda^2 x_0 \\ x_3 &= \lambda x_2 = \lambda^3 x_0 \end{aligned}

We prove by induction that $x_n = \lambda^n x_0$

  • Base case $n=0$, $x_0 = \lambda^0 x_0 = x_0$
  • Induction hypothesis Assume $x_k = \lambda^k x_0$ for $k\leq n$. We show that for $n+1$ step \[ \begin{aligned} x_{n+1}&=\lambda x_n \\ x_{n+1}&=\lambda \lambda^n x_0 \\ x_{n+1}&=\lambda^{n+1} x_0 \end{aligned} \]

So by induction

\[ \begin{aligned} V = (x_0,x_1,x_2,\dots) &= (x_0,\lambda x_0,\lambda^2x_0,\dots) \\ &= x_0 (1,\lambda,\lambda^2,\dots) \end{aligned} \]

It has eigenvectors of the form

\[ (1,\lambda,\lambda_2,\lambda_3,\dots) \]

Want to find $\lambda$

Since, $v\in V$, so coordinates satisfy recursion formula

\begin{aligned} x_{n+2} &= x_{n+1} x_n \\ \lambda^{n+2} &= \lambda^{n+1} +\lambda^n \end{aligned}

Solve for $\lambda^n(\lambda^2 -\lambda -1) = 0$