Proof by mathematical induction - Fibonacci numbers and matrices Using mathematical induction I am to prove:
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right)^n $ = 
$ \left( \begin{array}{ccc}
F_{n+1} & F_n  \\
F_n & F_{n-1}  \end{array} \right) $
where $F_k$ represents the $k^{th}$ Fibonacci number.
my base case is $n =2$
LHS: $ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right) \times$ 
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right) $$=$
$ \left( \begin{array}{ccc}
2 & 1 \\
1 & 1  \end{array} \right) $
RHS: $ \left( \begin{array}{ccc}
F_3 & F_2 \\
F_2 & F_1  \end{array} \right) $$=$
$ \left( \begin{array}{ccc}
2 & 1 \\
1 & 1  \end{array} \right) $
So $n = k + 1$
$ \left( \begin{array}{ccc}
F_{k+2} & F_{k+1} \\
F_{k+1} & F_k  \end{array} \right) $
So for my inductive step I did:
$ \left( \begin{array}{ccc}
F_{k+1} & F_k \\
F_k & F_{k-1}  \end{array} \right) $ $+$
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right)^{k+1} $
And now I'm not sure where to proceed from here. Can anyone point me in the right direction? Assuming my previous work is correct.
 A: To prove it for $n=1$ you just need to verify that
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right)^1 $ = 
$ \left( \begin{array}{ccc}
F_2 & F_1  \\
F_1 & F_0  \end{array} \right) $
which is trivial.
After you established the base case, you only need to show that assuming it holds for $n$ it also holds for $n+1$.
So assume
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right)^n $ = 
$ \left( \begin{array}{ccc}
F_{n+1} & F_n  \\
F_n & F_{n-1}  \end{array} \right) $
and try to prove
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right)^{n+1} $ = 
$ \left( \begin{array}{ccc}
F_{n+2} & F_{n+1}  \\
F_{n+1} & F_n  \end{array} \right) $
Hint: Write $ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right)^{n+1} $ as $ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right)^n $$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0  \end{array} \right) $.
A: Inductive proof:
For $n=1$ is true, as the OP correctly observed.
Assume that it is true for $n=k$. Then
$$
\left(\begin{matrix} 1& 1 \\ 1& 0\end{matrix}\right)^k=\left(\begin{matrix} F_{k+1}& F_k \\ 
F_k& F_{k-1}\end{matrix}\right)
$$
Then for $n=k+1$ we have
\begin{align}
\left(\begin{matrix} 1& 1 \\ 1& 0\end{matrix}\right)^{k+1}&=\left(\begin{matrix} 1& 1 \\ 1& 0\end{matrix}\right)^{k}\left(\begin{matrix} 1& 1 \\ 1& 0\end{matrix}\right)
=\left(\begin{matrix} F_{k+1}& F_k \\ 
F_k& F_{k-1}\end{matrix}\right)\left(\begin{matrix} 1& 1 \\ 1& 0\end{matrix}\right)=
\left(\begin{matrix} F_k+F_{k+1}& F_{k+1} \\ F_{k-1}+F_{k}& F_k\end{matrix}\right)\\ &=
\left(\begin{matrix} F_{k+2}& F_{k+1} \\ F_{k+1}& F_k\end{matrix}\right),
\end{align}
and hence it is true for $n=k+1$. Note that in the last equality above we used the recursive definition of Fibonacci sequence. 
