<s>[INST] How to prove that the Binet formula gives the terms of the Fibonacci Sequence? This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n > 1$,  where $u_0 = 0$ and $u_1 = 1$. 
Show that

$$u_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}.$$ 

Please help me with its proof. Thank you.
 [/INST] Let 
$$A=\begin{pmatrix}
1 & 1 \\ 1 & 0 
\end{pmatrix}$$
$$M_n =
\begin{pmatrix}
F_{n+1} & F_n \\ F_n & F_{n-1}
\end{pmatrix}$$
By induction, you can show that $M_n=A^n$.  Now, the eigenvalues of $A$ satisfy $\lambda^2-\lambda-1=0$. Let them be $\lambda_1$ and $\lambda_2$. 
$A$ can be diagonalized and written as $A=SBS^{-1}$, where $B=\begin{pmatrix}
\lambda_1 & 0\\ 0 & \lambda_2
\end{pmatrix}$, $S=\begin{pmatrix}
\lambda_1 & \lambda_2 \\ 1 & 1
\end{pmatrix}$
 Thus,
$$A^n = SBS^{-1}SBS^{-1}SBS^{-1}SBS^{-1}.... = SB^nS^{-1}$$
$$=\begin{pmatrix}
\lambda_1 & \lambda_2 \\ 1 & 1
\end{pmatrix}\begin{pmatrix}
\lambda_1^n & 0\\ 0 & \lambda_2^n
\end{pmatrix}(\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}
1 & -\lambda_2 \\ -1 & \lambda_1
\end{pmatrix})$$
$$=\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}
\lambda_1 & \lambda_2 \\ 1 & 1
\end{pmatrix}\begin{pmatrix}
\lambda_1^n & -\lambda_1^n\lambda_2\\ -\lambda_2^n & \lambda_2^n\lambda_1
\end{pmatrix}$$
$$=\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}
\lambda_1^{n+1}-\lambda_2^{n+1} & -\lambda_1\lambda_2(\lambda_1^n-\lambda_2^n)\\ \lambda_1^n-\lambda_2^n &-\lambda_1\lambda_2(\lambda_1^{n-1}-\lambda_2^{n-1})
\end{pmatrix}$$
Using $\lambda_1\lambda_2=-1$, $A^n =
\begin{pmatrix}
F_{n+1} & F_n \\ F_n & F_{n-1}
\end{pmatrix}$, $\lambda_1=\frac{1+\sqrt{5}}{2}$ and  $\lambda_2=\frac{1-\sqrt{5}}{2}$, we get
$$\begin{pmatrix}
F_{n+1} & F_n \\ F_n & F_{n-1}
\end{pmatrix} = \frac{1}{\sqrt{5}}\begin{pmatrix}
\lambda_1^{n+1}-\lambda_2^{n+1} &\lambda_1^n-\lambda_2^n\\ \lambda_1^n-\lambda_2^n &\lambda_1^{n-1}-\lambda_2^{n-1}
\end{pmatrix}$$
Which gives us $F_n=\frac{\lambda_1^n-\lambda_2^n}{\sqrt{5}}$, as required.
</s>