Fibonacci numbers: proof4 I need to proove the following
$F_{n+k}=F_{k-1}F_{n}+F_{k}F_{n+1}$
Firstly, I wanted to use mathematic induction, but I do not know, to which letter ($n$ or $k$) should be $1$ added, or it does not matter?
I also tried to find out the solution on the Internet, but unsuccessfully.
Thanks
 A: There are a couple of things you need to note:


*

*The proposition you're assuming is $P(k)$ where $n, k \in \mathbb Z^+$

*You need to set the "domain" as $k\geq2$ (i.e. your base case will be $P(2)$)

*You need to use strong mathematical induction for this. You should consider two consecutive generic cases such as $P(m)$ and $P(m+1)$ and show that if they hold true, then $P(m+2)$ will also hold true for all $m \in \mathbb Z^+$


Does this help?
Here is the proof:
$$P(k): F_{n+k}=F_{k-1}F_{n}+F_{k}F_{n+1}$$
$$
\begin{align}
P(2): F_{n+2} 
&= F_{1}F_{n}+F_{1}F_{n+1}\\[1em]
&= 1\cdot F_{n}+1\cdot F_{n+1}\\[1em]
&= F_{n} + F_{n+1}\\[1em]
&= F_{n+2}\tag{{P(2) is true}}\\[1em]
\end{align}
$$
$$P(m): F_{n+m}=F_{m-1}F_{n}+F_{m}F_{n+1}\tag{1}$$
$$P(m+1): F_{n+m+1}=F_{m}F_{n}+F_{m+1}F_{n+1}\tag{2}$$
$$P(m+2): F_{n+m+2} = F_{m+1}F_{n}+F_{m+2}F_{n+1}\tag{{Show this}}$$
$$
\begin{align}
F_{n+m+2}
&= F_{n+m}+F_{n+m+1}\\[1em]
&= F_{m-1}F_{n}+F_{m}F_{n+1}+F_{m}F_{n}+F_{m+1}F_{n+1}\tag{using (1) and (2)}\\[1em]
&= F_{n}(F_{m-1}+F_{m})+F_{n+1}(F_{m}+F_{m+1})\\[1em]
&= F_{m+1}F_{n}+F_{m+2}F_{n+1}\\[1em]
\end{align}
$$
$\implies P(m+2)$ holds true.
$\implies P(k)$ holds true.
