# Induction on 2 numbers

Show that for the Fibonacci numbers it holds that

$f_{x+y}=f_{y+1}f_{x}+f_{y}f_{x-1}$ for $x\ge 2, y\ge 1$

The proof goes as follows:

First we show that the claim holds for all $x\ge2$,$y=1$ and that it holds for $x\ge2, y=2$(easy)

In the Induction step we take $y\ge2, x\ge2$. It holds that

$f_{x+(y+1)}=f_{x+y}+f_{x+(y-1)}=f_{y+1}f_x+f_yf_{x-1}+f_yf_x+f_{y-1}f_{x-1}$ by the induction hypothesis

$=f_{y+2}f_x+f_{y+1}f_{x-1}$

Is this really a complete proof? I know that there are several ways to do an induction on $2$ numbers. But these usually involve an induction step on each variable or an induction on the sum of both.But in this one we never really do anything with $a$.

Could someone please explain/motivate this or just give me some reference for this kind of induction?

• Looks good, although I think you meant $\ldots + f_{y-1}f_{x-1}$, not $\ldots + f_{y-1}f_{x-y}$. – Théophile Nov 27 '17 at 18:34
• @Théophile Yes,I edited it – Blablablu Nov 27 '17 at 18:36
• It's self answered question, neat. – Abr001am Nov 27 '17 at 18:47
• A small quibble: the condition for the induction step should say that $y\geq2,$ not $3.$ – David K Nov 27 '17 at 19:23
• @DavidK Thanks! Edited – Blablablu Nov 27 '17 at 19:47

Actually, you're not doing induction on two variables here at all. You're only doing induction on $y$, while $x$ is assumed to be arbitrary. But, as such, it is a good proof!

• The addition is associative so fibonacci(x+(y+1))=fibonacci(y+(x+1)) – Abr001am Nov 27 '17 at 18:49
• @Bram28 Isn't the second base case necessary since we use the induction hypothesis for $y$ and for $y-1$? – Blablablu Nov 27 '17 at 18:51
• Both base case are needed. And both base cases are referred to. And both base cases are omitted with a blithe "easy"..."First we show that the claim holds for all x≥2,y=1 (first base case) and that it holds for x≥2,y=2 (second base case)" – fleablood Nov 27 '17 at 18:59
• @fleablood Thank you! The "easy" was just because I didn't want to type down everything, I wanted to mention, that the computation for both base cases is not my problem here. – Blablablu Nov 27 '17 at 19:02
• Oh, right, of course, both base cases are needed, sorry about that! – Bram28 Nov 27 '17 at 19:03

It's subtle but this induction is not doing: Assume true for $x$ and assume true for $y$ then show it is true for $x+1$ and $y+1$.

That would not be valid as that proves only for $x$ and $y$ where $x - y = constant$.

BUT this is actually doing something different. It is assuming it is true for $n = x+y$ and showing it is therefore true for $n = (x+y) + 1 = (x+1) + y = x + (y+1)$.

That is valid.

====

On second reading, I see Bram28, is correct and this is only an induction on the variable $y$. and not on $x$ at all.

To see that this proof is complete, you should note the base cases (for $y= 1; x\ge 2$ and $y= 2; x\ge 2$)[1] was for any arbitrary $x$ and not for an $x = 2$. So induction on $x$ is unnecesary.

I'm going to leave my answer up, because I think it illustrates a good point of looking at an induction proof involves carefully evaluating what the variable being inducted upon is; not merely what it looks like.

The poof could have been identically done on $x+y \implies x + y+ 1$ (only the framing of the base case would differ).

[1] Both base cases were omitted which isn't really fair.

$y=1; f_{x+y}=f_{x+1}=1*f_x + 1*f_{x-1}=f_2f_x + f_1f_{x-1}=f_yf_x + f_{y+1}f_x$.

$y=2; f_{x+y}=f_{x+2}=f_{x+1} + f_x=f_x + f_{x-1} + f_x = 2*f_{x} + 1*f_{x-1} = f_3*f_x + f_2*f_{x-1} = f_{y+1}f_x + f(y)*f_{x-1}$.

• Thank you, that's exactly what confused me aswell – Blablablu Nov 27 '17 at 18:59