Fibonacci sequence and eigenvalues 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}$?
 A: 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)
$$
A: A proof of Binet's formula which doesn't make use of matrices can be found here: http://www.cut-the-knot.org/proofs/BinetFormula.shtml.
A: Caution I decided to include the following because it was too long for a comment.  I believe it to be correct but I'm not 100%.  If appropriate I will delete / edit 
Let $ \boldsymbol{b}=\begin{bmatrix}x_{n+1}\\x_n\end{bmatrix}$ and $\boldsymbol{x} = \begin{bmatrix}x_1\\x_0\end{bmatrix}$
You have the system $\boldsymbol{b} = F^n \boldsymbol{x}$
Form the matrix $P$ whose columns are the eigenvectors of $F$.
Use the substitution $\boldsymbol{x}=P\boldsymbol{u}$ where $\boldsymbol{u}$ is a column vector.
You now have $$\boldsymbol{b} = F^n \boldsymbol{x}\\\boldsymbol{b} = F^n P\boldsymbol{u}\\P^{-1}\boldsymbol{b} = P^{-1}F^n P\boldsymbol{u}\\P^{-1}\boldsymbol{b}=D^n\boldsymbol{u}$$
Where $D$ is a matrix whose diagonal elements are the eigenvalues of $F$
As the $D$ is diagonal the system of equations is decoupled and solvable separately. 
I believe you are asking that, as the components of $\boldsymbol{u}$ inevitably end up multiplied by the powers of eigenvalues, is there a short cut? I don't know of any direct method.
Hope it helps the discussion anyways.
