I'm learning about eigenvectors and values, and one of the excercises in my book tackles the fibonacci recursion from this angle.
Let $F = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n
\quad\text{ then }\quad \begin{bmatrix}x_{n+1}\\x_n\end{bmatrix} = F^n
\begin{bmatrix}x_1\\x_0\end{bmatrix}
$
To obtain a closed formula for $x_n$, I've obtained the eigenvalues and vectors of $F$, diagonalized it into $PDP^{-1}$ (where $P$ is the eigenvector matrix and $D$ is $\operatorname{diag}(\operatorname{eig}(F))$ and calculated the product of $PD^nP^{-1}$.
I feel like I'm missing something. The eigenvalues are there in the closed formula. Is there a way to deduce the formula from the eigenvalues without calculating $P^{-1}$ and $PDP^{-1}$?
Best Answer
No, you don't need to explicitly compute $P^{-1}$ and multiply out $PD^nP^{-1}$ in order to get the closed formula for the Fibonacci numbers, but if you avoid it you still need to do something similar.
Call that matrix $A=(\begin{smallmatrix}1&1\\1&0\end{smallmatrix})$ (for some reason the question puts $x_{n+1}$ above $x_n$ in the column vector, so everything will be turned upside down: the normal thing would have been to put it below, and use the matrix $(\begin{smallmatrix}0&1\\1&1\end{smallmatrix})$ instead). Its eigenvalues $\phi_+=\frac{1+\sqrt5}2$ and $\phi_-=\frac{1-\sqrt5}2$, and choose eigenvectors for each of these eigenvalues: $v=(\begin{smallmatrix}\phi_+\\1\end{smallmatrix})$ and $w=(\begin{smallmatrix}\phi_-\\1\end{smallmatrix})$; your change of basis matrix $P$ is then formed by taking the coordinates of $v,w$ as columns: $P=(\begin{smallmatrix}\phi_+&\phi_-\\1&1\\\end{smallmatrix})$. The fact that $v$ and $w$ are eigenvectors means that you know the general expression for the terms of sequences $(a_n)_{n\in\Bbb N}$ and $(b_n)_{n\in\Bbb N}$, defined using the same recurrence relation as for the Fibonacci sequence, but contrary to it with the special initial conditions $a_0=1,a_1=\phi_+$ respectively $b_0=1,b_1=\phi_-$: from $A^n\cdot v=\phi_+^nv$ for all $n$ one gets $a_n=\phi_+^n$, and from $A^n\cdot w=\phi_-^nw$ one gets $b_n=\phi_-^n$ (the formula leaves nothing but the power of the eigenvalue because our eigenvectors were conveniently chosen to have bottom entry equal to$~1$).
But the Fibonacci sequence $(f_n)_{n\in\Bbb N}$ has initial values $f_0=0$ and $f_1=1$, so you want to know (the bottom entry of) the matrix product $A^n\cdot(\begin{smallmatrix}1\\0\end{smallmatrix})$ for any$~n$. Since multiplication by $A^n$ is linear, we can find this by writing $(\begin{smallmatrix}1\\0\end{smallmatrix})$ as a linear combination of $v$ and $w$; then the expression for $f_n$ will be the corresponding linear combination of $v$ and $w$. The relation $\mu v+\nu w=(\begin{smallmatrix}0\\1\end{smallmatrix})$ can be written as $P\cdot(\begin{smallmatrix}\mu\\\nu\end{smallmatrix})=(\begin{smallmatrix}1\\0\end{smallmatrix})$ and is a $2\times2$ linear system of equations. The solution is $(\begin{smallmatrix}\mu\\\nu\end{smallmatrix})=P^{-1}\cdot(\begin{smallmatrix}1\\0\end{smallmatrix})$, but can be found using Gaussian elimination without computing $P^{-1}$: the result is $\mu=\frac1{\sqrt5}$ and $\nu=-\frac1{\sqrt5}$. Then finally $$ f_n=\mu\phi_+^n+\nu\phi_-^n = \frac1{\sqrt5}\left((\frac{1+\sqrt5}2)^n-(\frac{1-\sqrt5}2)^n\right) $$