Show that $\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n$ for all $n ∈ N$. The Fibonacci numbers $F_n$ are recursively defined by
$F_0 = 0, F_1 = 1$
$F_{n+2} = F_{n+1} + F_n, n = 0,1,...$
i) Show that $\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n$ for all $n ∈ N$.
ii) Show that $F_0^2 + F_1^2 + ...+F_n^2 = F_n F_{n+1}$ for all $n ∈ N$.
iii) Show that $F_{n-1} F_{n+1} - F_n^2 = (-1)^n$ for all $n ∈ N$.
 A: Just try to prove those by induction on $n\in\mathbb{N}$.
For example, the "induction step" for the second exercise is:
Suppose that $F_0^2+\cdots+F_n^2=F_nF_{n+1}$, then $$F_0^2+\cdots+F_n^2+F_{n+1}^2=F_nF_{n+1}+F_{n+1}^2=F_{n+1}(F_n+F_{n+1})=F_{n+1}F_{n+2}$$
Try the same approach in the other exercises. Don't forget the base cases.
A: Hint: 
(i) Easy induction.
(ii)
Note that
$$
\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}^2 = 
\begin{bmatrix}F_{n+1}^2+F_n^2&*\\*&*\end{bmatrix} 
$$
(iii) Take determinants.
A: i) Diagonalize the RHS matrix:
$$\begin{pmatrix}1&1\\ 1&0\end{pmatrix}^n=
\begin{pmatrix}\psi&\phi\\ 1&1\end{pmatrix}
\begin{pmatrix}\psi^n &0\\ 0&\phi^n\end{pmatrix}
\begin{pmatrix}-\frac{1}{\sqrt{5}}&\frac{\phi}{\sqrt{5}}\\ \frac1{\sqrt{5}}&-\frac{\psi}{\sqrt{5}}\end{pmatrix}=\\
\begin{pmatrix}\psi^{n+1}&\phi^{n+1}\\ \psi^n&\phi^n\end{pmatrix}
\begin{pmatrix}-\frac{1}{\sqrt{5}}&\frac{\phi}{\sqrt{5}}\\ \frac1{\sqrt{5}}&-\frac{\psi}{\sqrt{5}}\end{pmatrix}=\\
\begin{pmatrix}\frac{\phi^{n+1}-\psi^{n+1}}{\sqrt{5}}&\frac{\phi^n-\psi^n}{\sqrt{5}}\\ \frac{\phi^n-\psi^n}{\sqrt{5}}&\frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}\end{pmatrix}=\\
\begin{pmatrix}F_{n+1}&F_n\\ F_n&F_{n-1}\end{pmatrix}.$$
Note: $\phi\cdot \psi=-1$.
