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