# For Fibonacci sequence, $f_{m+n+1}=f_m f_n+ f_{m+1}f_{n+1}$ [Proof Verification] [duplicate]

Theorem:

For Fibonacci sequence, $$f_{m+n+1}=f_m f_n+ f_{m+1}f_{n+1}$$

Proof:

Let $$P(n)$$ is the statement $$\forall m \in \mathbb{N}(f_{m+n+1}=f_m f_n+ f_{m+1}f_{n+1})$$.

It is clear that $$P(0)$$ is true.

Assuming that $$P(k)$$ is true i.e. $$\forall m \in \mathbb{N}(f_{m+k+1}=f_m f_k+ f_{m+1}f_{k+1})$$.

Since $$P(k)$$ is true for all $$m$$, then $$P(k)$$ is true for $$(m+1)$$ too.

Substitute $$(m+1)$$ for $$m$$, we have $$f_{(m+1)+k+1}=f_{m+1} f_k+ f_{(m+1)+1}f_{k+1}=f_{m+1} f_k+ f_{m+2}f_{k+1}$$.

$$\iff f_{(m+1)+k+1}=f_{m+1} f_k+ f_{m+2}f_{k+1}$$

We now prove $$P(k+1)$$ is true.

$$f_{m+(k+1)+1}=f_{(m+1)+k+1}=f_{m+1} f_k+ f_{m+2}f_{k+1}$$

$$=f_{m+1} f_k+(f_{m+1}+f_m)f_{k+1}$$

$$=f_{m+1} f_k+f_{m+1} f_{k+1}+f_m f_{k+1}$$

$$=f_{m+1}(f_k+f_{k+1})+f_m f_{k+1}$$

$$=f_{m+1} f_{k+2} + f_m f_{k+1}$$

$$=f_m f_{k+1}+f_{m+1} f_{k+2}$$

$$=f_m f_{k+1}+f_{m+1} f_{(k+1)+1}$$.

To sum up, $$f_{m+(k+1)+1}=f_m f_{k+1}+f_{m+1} f_{(k+1)+1}$$. This implies $$P(k+1)$$ is true.

By principle of induction, $$P(n)$$ is true for all $$n \in \mathbb{N}$$.

• Looks right to me – Alex Zorn Apr 2 '18 at 3:54
• – Bill Dubuque Nov 19 '19 at 15:51

Your proof is correct. You may fix $m$ and just focus on $n$ to save some effort.
• When i said "Substitue $(m+1)$ for $m$", I still work on the indentity $P(k)$. After a few lines, then I wrote "We now prove $P(k+1)$ is true. $f_{m+(k+1)+1}=f_{(m+1)+k+1}=f_{m+1} f_k+ f_{m+2}f_{k+1}$....". Please have a closer look! – LE Anh Dung Apr 2 '18 at 4:03
• Since $P(k)$ is true for all $m$, then $P(k)$ is true for $m+1$ too. – LE Anh Dung Apr 2 '18 at 4:05
• @DungLe: Since you replace $m$ by $m+1$ before the inductive step, you have proven that the inductive step holds for all $m\geq 2$. You still need to show that the inductive step also holds with $m=1$ (this is trivial, but still needs to be done to complete the proof). – Prasun Biswas Apr 2 '18 at 4:30