1
$\begingroup$

Today when I was proving the identity with Fibonacci sequence, namely: $$F_{m+n+1}=F_{m+1}F_{n+1}+F_{m}F_{n} \quad \text{for} \ m,n \geqslant 0$$ I have used mathematical induction. But we know that if we have some property which depends on natural numbers, namely $P(n)$ and we have needed properties on $P(n)$ we can prove that $P(n)$ holds for any $n\in \mathbb{N}$ -- this is the principle of math induction.

However in that post I have applied mathematical induction on $n$ and proved that it holds for any $n\in \mathbb{N}\cup \{0\}$ (the case $n=0$ also true).

However, we should prove that above identity is true for any $m,n\geqslant 0$, but in my proof i have done it only for natural parameter $n$. What about $m$?

Can anyone explain this subtle moment, please?

$\endgroup$
6
  • 1
    $\begingroup$ If you have shown by induction on $n$, that for any given $m$ , the statement $\forall n \;[S(n,m)],$ then you have $\forall m\;\forall n\;[S(n,m)]$ and you are done. $\endgroup$ Nov 28 '17 at 19:29
  • $\begingroup$ @DanielWainfleet, Am I correct that you fixed $m$ and apply induction on $n$, right? $\endgroup$
    – ZFR
    Nov 28 '17 at 19:50
  • 1
    $\begingroup$ Yes. Is that what you did? You say you proved it for all $n$. For which $m$ did you prove it for all $n$? $\endgroup$ Nov 28 '17 at 19:53
  • 1
    $\begingroup$ @DanielWainfleet, on that time i did not pay attention to $m$ but right now i realize that we should fix $m$ then apply induction on $n$. $\endgroup$
    – ZFR
    Nov 28 '17 at 19:56
  • 2
    $\begingroup$ And if that works then there is no more work needed. In some problems we show that $S(0,0)$ holds and that $S(n,m)\implies [S(n+1,m)\land S(n,m+1)]$ for all $m,n\geq 0.$ In your Q, $S(m,n)$ and $S(n,m)$ are the same thing so there's only half as much induction to do. $\endgroup$ Nov 28 '17 at 20:18
0
$\begingroup$

You have to use a double $induction$. First you use it on $m$ and, recoursively, you apply it to $n$. I mean, when you write about the case $m=0$ you have to reason using induction on $n$ (because you have supposed to have $m$ fixed). Then do the same for $P(m)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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