# 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, "url": "https://math.stackexchange.com/questions/487129/the-principle-of-mathematical-induction", "fetch_time": 1611400891000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2021-04/segments/1610703537796.45/warc/CC-MAIN-20210123094754-20210123124754-00708.warc.gz", "warc_record_offset": 429639817, "warc_record_length": 33395, "token_count": 874, "char_count": 1974, "score": 4.5, "int_score": 4, "crawl": "CC-MAIN-2021-04", "snapshot_type": "latest", "language": "en", "language_score": 0.567506730556488, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00057-of-00064.parquet"}