Using linear algebra, how is the Binet formula (for finding the nth Fibonacci number) derived? If possible, please refrain from any type of proof besides linear algebra. So, using the recursion formula $F_{n+1} = F_{n-1} + F_n$, for $n\gt 1$, and where $F_0 = 0$ and $F_1 = 1$, and the Fibonacci matrix, derive the golden ratio and ultimately the Binet formula. 
 A: The Fibonacci numbers are defined by a second-order linear recurrence equation:
$$F_{n+2} = F_{n+1} + F_n$$
This means we can treat the solution of $F_n$ in terms of $n$ as a problem in linear algebra involving only $2$-dimensional vectors. In some sense, what we are doing is modelling this as a dynamical process on a $2$-dimensional state space.
Let $V = \mathbb{R}^2$. We define a linear operator $T : V \to V$ by
$$T(x, y) = (y, x + y)$$
Notice that $T(F_{n}, F_{n+1}) = (F_{n+1}, F_{n+2})$, so you can think of $V$ as being a sliding $2$-entry window on the Fibonacci sequence and $T$ as the operator which advances the window along the Fibonacci sequence. The initial conditions $F_0 = 0, F_1 = 1$ then imply that
$$T^n(0, 1) = (F_n, F_{n+1})$$
so all we need to do to find $F_n$ in terms of $n$ is to find an effective way to compute iterates of the operator $T$!
Now, we get our hands dirty and represent $T$ as a matrix:
$$T = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$$
Imagine if we could somehow find an invertible matrix $P$ and a diagonal matrix $D$ such that $T = P D P^{-1}$; then, by matrix algebra, we would have $T^n = P D^n P^{-1}$, and it is easy to compute powers of diagonal matrices. The theory of eigenvectors and eigenvalues gives us one way to find such a factorisation of $T$. Notice that 
$$\det (T - x I) = \det (P(D - x I)P^{-1}) = (\det P)(\det (D - x I))(\det P^{-1}) = \det (D - x I)$$
but a simple calculation shows
$$\det (D - x I) = \det \begin{pmatrix} \lambda_1 - x & 0 \\ 0 & \lambda_2 - x \end{pmatrix} = (\lambda_1 - x)(\lambda_2 - x)$$
so whatever $\lambda_1$ and $\lambda_2$ are, they must be the zeros of the polynomial
$$\det (T - x I) = \det \begin{pmatrix} -x & 1 \\ 1 & 1 - x \end{pmatrix} = x^2 - x - 1$$
which, surprise surprise, is the minimal polynomial of the golden ratio. So let $\lambda_1 = \frac{1}{2} (1 + \sqrt{5})$ and $\lambda_2 = \frac{1}{2} (1 - \sqrt{5})$. These are the eigenvalues of $T$. By construction, $\det (T - \lambda_1 I) = \det (T - \lambda_2 I) = 0$, so there must be non-zero vectors $\begin{pmatrix} x_1 \\ y_1 \end{pmatrix}$ and $\begin{pmatrix} x_2 \\ y_2 \end{pmatrix}$ such that
$$
T
\begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = 
\lambda_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix}
$$
$$
T
\begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = 
\lambda_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix}
$$
These vectors are called the eigenvectors of $T$. I leave you to verify that $x_1 = \lambda_1 - 1$, $y_1 = 1$, $x_2 = \lambda_2 - 1$, $y_2 = 1$ works, but there are other solutions.
Define the matrix $P$ by
$$P = \begin{pmatrix} x_1 & x_2 \\ y_1 & y_2 \end{pmatrix}$$
Notice that
$$\begin{pmatrix} x \\ y \end{pmatrix} = 
\alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} +
\alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = 
P \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$
so by linearity we have
$$T \begin{pmatrix} x \\ y \end{pmatrix} = 
\lambda_1 \alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} +
\lambda_2 \alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = 
P \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$
but we can invert $P$ to find $\alpha_1$ and $\alpha_2$ in terms of $x$ and $y$, so we have obtained the desired factorisation of $T$ as $P D P^{-1}$ with $D$ diagonal. Putting everything together, we get the formula
$$T^n = P \begin{pmatrix} {\lambda_1}^n & 0 \\ 0 & {\lambda_2}^n \end{pmatrix} P^{-1}$$
and applying this to the vector $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ gives Binet's formula.
A: I am not sure to which extent this will be helpful for OP, but I'll post this anyway. This is basically the same solution as the one posted by Zhen Lin, but without any explicit reference to eigenvalues or eigenvectors.

So the sequence given by $F_{n+2}=F_{n+1}+F_n$ seems to be complicated. But there is a wide class of sequences we understand very good - geometric progressions.
Let us ask the question whether we can modify the sequence $F_n$ to get a geometric progression. E.g. we can ask whether there is an $x$ such that the sequcence $G_n=xF_n+F_{n-1}$ is a geometric progression.
From
$$\begin{align}
F_{n+1}&=F_n+F_{n-1}\\
F_{n}&=F_{n-1}+F_{n-2}
\end{align}
$$
we get
$$G_{n+1}=xF_{n+1}+F_n=xF_n+(x+1)F_{n-1}+F_{n-2}=
xF_n+(x+1)F_{n-1}+F_n-F_{n-1}=(x+1)F_n+xF_{n-1}.$$
If we want the RHS to be a multiple of $G_n$, then we must have
$$\frac{x+1}x=x,$$
i.e. $x+1=x^2$ or $x^2-x-1=0$, which has the two solutions $\lambda_{1,2}=\frac{1\pm\sqrt5}2$.
Notice that $\lambda_1+\lambda_2=1$, $\lambda_1\lambda_2=-1$.
For any of the above values we have
$$G_{n+1}=(\lambda+1)F_n+\lambda F_{n-1}=\lambda\left(\frac{\lambda+1}\lambda F_n+F_{n-1}\right)=\lambda G_n.$$
We also have $G_1=\lambda$, $G_0=1$.
So we get
$$
\begin{align}
\lambda_1F_{n}+F_{n-1}&=\lambda_1^n\\
\lambda_2F_{n}+F_{n-1}&=\lambda_2^n
\end{align}
$$
If we subtract the above two equations, we get
$$(\lambda_1-\lambda_2)F_{n}=\lambda_1^n-\lambda_2^n$$
which gives
$$F_n=\frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}.$$

In the solution, which used the diagonal form and eigenvalues, we did not have to guess, that it is possible to obtain geometric progressions combining Fibonacci sequence and shifted Fibonacci sequence - we get this fact from that diagonal matrix.
Or we can look at this the other way round - many applications of diagonal matrices similar to given matrix (e.g. in linear recurrences, ordinary differential equations) can be viewed as an effort to transform the original problem to a simpler form; in this case the simpler form was a geometric progression.
