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.

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) $.
