# Proof with mathematical induction: $F_{m+n+1}=F_{m+1}F_{n+1}+F_{m}F_{n} \quad \text{for} \ m,n \geqslant 0$

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?

• 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. Nov 28 '17 at 19:29
• @DanielWainfleet, Am I correct that you fixed $m$ and apply induction on $n$, right?
– ZFR
Nov 28 '17 at 19:50
• Yes. Is that what you did? You say you proved it for all $n$. For which $m$ did you prove it for all $n$? Nov 28 '17 at 19:53
• @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$.
– ZFR
Nov 28 '17 at 19:56
• 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. Nov 28 '17 at 20:18

## 1 Answer

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