Induction proof of Fibonacci numbers

Question

The Fibonacci numbers can be defined recursively by letting
\begin{align} F_{0}=0, \ F_{1}=1\end{align} Then for every natural number $n\geq 2$, \begin{align} F_{n}= F_{n-2}+F_{n-1}\end{align}

Prove that for all $n,k\in\mathbb{N}$, \begin{align} F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}. \end{align} So far this is my proof.

First for $k=1$, \begin{align}F_{n+1}=F_{1}F_{n+1}+F_{0}F_{n-1}\end{align}\begin{align} =1{\cdot}F_{n+1}+0{\cdot}F_{n-1}\end{align} \begin{align} =F_{n+1} \end{align} Now let $k\in\mathbb{N}$ with $k\geq2$ and assume that \begin{align}F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}\end{align}

I'm unsure about whether \begin{align} F_{n+(k+1)}=F_{k+1}F_{n+1}+F_{k}F_{n} \end{align} is true or not because if so, then \begin{align} F_{n+(k+1)}=F_{(n+1)+k}=F_{k}F_{n+2}+F_{k-1}F_{n+1} \end{align} could be true as well. Any advice about how to finish this induction would be very helpful.

Answer 1

Suppose by induction that $$ F_{n+k}=F_kF_{n+1}+F_{k-1}F_n\quad (1) $$ holds for all for numbers $N\leq k$, and let us proof for $k+1$. Hence, as $(1)$ holds for all $N\leq k$, we have $$ F_{n+k-1}=F_{k-1}F_{n+1}+F_{k-2}F_n\quad (2) $$ Summing $(1)$ and $(2)$ we obtain \begin{eqnarray} F_{n+k}+F_{n+k-1}&=&F_kF_{n+1}+F_{k-1}F_n+F_{k-1}F_{n+1}+F_{k-2}F_n\\ &=&(F_k+F_{k-1})F_{n+1}+(F_{k-1}+F_{k-2})F_n. \end{eqnarray} By the definition of Fibonacci sequence we have $F_k=F_{k-2}+F_{k-1}$, $F_{k+1}=F_{k-1}+F_{k}$ and $F_{n+k+1}=F_{n+k}+F_{n+k-1}$. Hence, $$ F_{n+k+1}=F_{k+1}F_{n+1}+F_kF_n. $$ Which is $(1)$ for $k+1$.

Answer 2

Let $M$ be the $2\times2$ matrix with top-row entries $1,1$ and botton-row entries $1,0$ (from left to right): $$ M = \pmatrix { 1 & 1 \\ 1 & 0 } $$

Prove by induction on $n\in \Bbb N$ that the top row of $M^n$ is $F_{n+1}, F_n$ and the bottom row is $F_n,F_{n-1}$: $$ {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}} $$ Compare the entries of $M^{n+k}$ with those of $(M^n\cdot M^k).$