# 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.

• Why are you summing the matrices? Commented Feb 28, 2014 at 11:13
• I was under the assumption that when proving by induction you add the LHS where $n = k+1$ to the RHS where $n=k$ Commented Feb 28, 2014 at 11:15
• Yes --- if you're trying to prove something about a sum. That's not the case here. What you want to do in an induction proof, is write down the induction hypothesis at the top of the page, the thing to be proved at the bottom of the page, and then fill in a logical argument that leads from the top to the bottom. Commented Feb 28, 2014 at 11:17
• See also: math.stackexchange.com/questions/61997/… )and other posts linked there) Commented Nov 7, 2015 at 19:57

## 2 Answers

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) . • Geez, I really managed to over-complicate this problem for myself! Thank you. Commented Feb 28, 2014 at 11:23 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+1we 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 forn=k+1\$. Note that in the last equality above we used the recursive definition of Fibonacci sequence.