# 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

HINT:

$$\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}$$

• After I multiplied \begin{bmatrix} 1 & 1\\ 1& 0 \end{bmatrix} to the right side I obtained \begin{bmatrix} F_{k+1}+F_k &F_{k+1}\\ F_{k}+F_{k-1} &F_k \end{bmatrix} but that's not my desired result. – Candy Pelagio Sep 8 '13 at 6:27
• @CandyPelagio, why shall we not use $F_{n+1}=F_n+F_{n-1}?$ – lab bhattacharjee Sep 8 '13 at 6:28
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}