1
$\begingroup$

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?

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

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!

$\endgroup$
  • $\begingroup$ The addition is associative so fibonacci(x+(y+1))=fibonacci(y+(x+1)) $\endgroup$ – Abr001am Nov 27 '17 at 18:49
  • $\begingroup$ @Bram28 Isn't the second base case necessary since we use the induction hypothesis for $y$ and for $y-1$? $\endgroup$ – Blablablu Nov 27 '17 at 18:51
  • 1
    $\begingroup$ 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)" $\endgroup$ – fleablood Nov 27 '17 at 18:59
  • $\begingroup$ @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. $\endgroup$ – Blablablu Nov 27 '17 at 19:02
  • $\begingroup$ Oh, right, of course, both base cases are needed, sorry about that! $\endgroup$ – Bram28 Nov 27 '17 at 19:03
1
$\begingroup$

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

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

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.