2
$\begingroup$

Please check my below proof. Thank your for your help!

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}$.

$\endgroup$
2
1
$\begingroup$

Your proof is correct. You may fix $m$ and just focus on $n$ to save some effort.

$\endgroup$
8
  • $\begingroup$ 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! $\endgroup$ – LE Anh Dung Apr 2 '18 at 4:03
  • $\begingroup$ Since $P(k)$ is true for all $m$, then $P(k)$ is true for $m+1$ too. $\endgroup$ – LE Anh Dung Apr 2 '18 at 4:05
  • $\begingroup$ So my proof is true, but the way i wrote it possibly causes some confusion. Is it right? $\endgroup$ – LE Anh Dung Apr 2 '18 at 4:22
  • $\begingroup$ Yes, you may save some work by just working on n. Your proof is correct as is but could be shorter. $\endgroup$ – Mohammad Riazi-Kermani Apr 2 '18 at 4:30
  • $\begingroup$ @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). $\endgroup$ – Prasun Biswas Apr 2 '18 at 4:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.