<s>[INST] How to prove Fibonacci sequence with matrices? How do you prove that:
$$
\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}^n
= 
\begin{pmatrix}
F_{n+1} & F_n\\
F_{n} & F_{n-1}
\end{pmatrix}$$
 [/INST] Let
$$A=\begin{pmatrix}
1 & 1 \\ 1 & 0 
\end{pmatrix}$$
And the Fibonacci numbers, defined by
$$\begin{eqnarray}
F_0&=&0\\
F_1&=&1\\
F_{n+1}&=&F_n+F_{n-1}
\end{eqnarray}$$
Then, by induction,
$$A^1=\begin{pmatrix}
1 & 1 \\ 1 & 0
\end{pmatrix} =
\begin{pmatrix}
F_2 & F_1 \\ F_1 & F_0
\end{pmatrix}$$
And if for $n$ the formula is true, then
$$A^{n+1}=A\,A^n=\begin{pmatrix}
1 & 1 \\ 1 & 0
\end{pmatrix}\begin{pmatrix}
F_{n+1} & F_{n} \\ F_{n} & F_{n-1}
\end{pmatrix}=\begin{pmatrix}
F_{n+1}+F_n & F_{n}+F_{n-1} \\  F_{n+1} & F_{n}
\end{pmatrix}=\begin{pmatrix}
F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n}
\end{pmatrix}$$
So, the induction step is true, and by induction, the formula is true for all $n>0$.
</s>