The question is
Let $( F_0, F_1, F_2,… )$ be the Fibonacci sequence defined by $F_0=0,\, F_1=1, and F_{n+1}=F_n+F_{n-1}$, n greater than or equal to 1. Prove the following identities.
$$\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^n =\begin{bmatrix}
F_{n+1} &F_n \\
F_n &F_{n-1}
\end{bmatrix}$$
This is what I tried.
Proof:
Base case: If $n=1$ the formula says
$$\begin{bmatrix}
1 & 1\\
1& 0
\end{bmatrix}^{1}=\begin{bmatrix}
F_{1+1} & F_1\\
F_1 &F_0
\end{bmatrix}=\begin{bmatrix}
1+0 & 1\\
1 & 0
\end{bmatrix}=\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}$$ which is true.
Inductive Step: Suppose the formula holds for $n=k$ i.e. that
$$\begin{bmatrix}
1 & 1\\
1& 0
\end{bmatrix}^{k}=\begin{bmatrix}
F_{k+1} &F_k\\
F_k &F_{k-1}
\end{bmatrix}$$ is true.
We have to show that the formula holds for $n=k+1$ that is
$$\begin{bmatrix}
1 &1 \\
1&0
\end{bmatrix}^{k+1}= \begin{bmatrix}
F_{k+2} & F_{k+1} \\
F_{k+1}&F_k
\end{bmatrix}$$ is true. Adding $\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{k+1}$ both sides give
$$\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^k + \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{k+1}= \begin{bmatrix}
F_{k+1} &F_k\\
F_k &F_{k-1}
\end{bmatrix} + \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{k+1}$$
This is where I'm stuck. From here I don't know how to proceed. Please let me know if I'm in the right direction.
Best Answer
HINT:
Instead of adding, multiply either sides of
$$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}^{k}=\begin{bmatrix} F_{k+1} &F_k\\ F_k &F_{k-1} \end{bmatrix}$$ by
$$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix} $$