Induction proof of Fibonacci numbers 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.
 A: 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$.
A: 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).$
