Fibonacci numbers: proof4

Question

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

Answer 1

There are a couple of things you need to note:

1. The proposition you're assuming is $P(k)$ where $n, k \in \mathbb Z^+$
2. You need to set the "domain" as $k\geq2$ (i.e. your base case will be $P(2)$)
3. 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.