# The Principle of Mathematical Induction

The question is

Let $( F_0, F_1, F_2,... )$ be the Fibonacci sequence defined by $F_0=0,\, F_1=1, and F_{n+1}=F_n+F_{n-1}$, n greater than or equal to 1. Prove the following identities. $$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n =\begin{bmatrix} F_{n+1} &F_n \\ F_n &F_{n-1} \end{bmatrix}$$ This is what I tried.

Proof: Base case: If $n=1$ the formula says $$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}^{1}=\begin{bmatrix} F_{1+1} & F_1\\ F_1 &F_0 \end{bmatrix}=\begin{bmatrix} 1+0 & 1\\ 1 & 0 \end{bmatrix}=\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}$$ which is true.

Inductive Step: Suppose the formula holds for $n=k$ i.e. that $$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}^{k}=\begin{bmatrix} F_{k+1} &F_k\\ F_k &F_{k-1} \end{bmatrix}$$ is true.

We have to show that the formula holds for $n=k+1$ that is $$\begin{bmatrix} 1 &1 \\ 1&0 \end{bmatrix}^{k+1}= \begin{bmatrix} F_{k+2} & F_{k+1} \\ F_{k+1}&F_k \end{bmatrix}$$ is true. Adding $\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1}$ both sides give $$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^k + \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1}= \begin{bmatrix} F_{k+1} &F_k\\ F_k &F_{k-1} \end{bmatrix} + \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1}$$ This is where I'm stuck. From here I don't know how to proceed. Please let me know if I'm in the right direction.

• I don't think proof-verification is a correct tag. – Parth Thakkar Sep 8 '13 at 6:09

$$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}^{k}=\begin{bmatrix} F_{k+1} &F_k\\ F_k &F_{k-1} \end{bmatrix}$$ by
$$\begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix}$$
• @CandyPelagio, why shall we not use $F_{n+1}=F_n+F_{n-1}?$ – lab bhattacharjee Sep 8 '13 at 6:28