discrete mathematics - 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.

Answer

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