# 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 thatx_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+1step \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\$