Question: > 
> 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?

Answer: 
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!
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}$.