<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] $$\begin{align}
F(n+1) &= 1\,F(n) + 1\,F(n-1)\\
F(n) &= 1\,F(n) + 0\,F(n-1)\\
\\
\begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F(n) \\ F(n - 1) \end{bmatrix} \\
\begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} \\
\\
\text{as well as} \\
\begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(0) \\ F(-1) \end{bmatrix} \\
\\
\text{from which it follows}\\
\begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) & F(0) \\ F(0) & F(-1) \end{bmatrix} \\
\\
\text{and choosing} \\
F(1) &= 1 \\
F(0) &= 0 \\
F(-1) &= 1
\end{align}$$
</s>