Fibonacci Proof by Induction

williampb

I've been having a lot of trouble with this proof lately:

Prove that,

F[itex]_{1}[/itex]F[itex]_{2}[/itex]+F[itex]_{2}[/itex]F[itex]_{3}[/itex]+...+F[itex]_{2n}[/itex]F[itex]_{2n+1}[/itex]=F[itex]^{2}_{2n+1}[/itex]-1

Where the subscript denotes which Fibonacci number it is. I'm not sure how to prove this by straight induction so what I did was first prove that,

F[itex]_{2}[/itex]+F[itex]_{4}[/itex]+...+F[itex]_{2n}[/itex]=F[itex]_{2n+1}[/itex]-1

And then used that in the other proof.

For F[itex]_{2}[/itex]+F[itex]_{4}[/itex]+...+F[itex]_{2n}[/itex]=F[itex]_{2n+1}[/itex]-1

First,
For n=1 (base case)

F[itex]_{2(1)}[/itex]=F[itex]_{2}[/itex]=1

Then,

F[itex]_{2(k+1)}[/itex]=F[itex]_{2(k+1)+1}[/itex]-1+F[itex]_{2(k+1)}[/itex]
=(F[itex]_{2k+3}[/itex]+F[itex]_{2k+2}[/itex])-1
=F[itex]_{2k+5}[/itex]-1 = F[itex]_{2(k+2)+1}[/itex]-1

Proving that F[itex]_{2k}[/itex]=F[itex]_{2k+1}[/itex]-1 for all k+1.

Now my question is, would this be a valid method for the proof first stated:

F[itex]_{2n}[/itex]F[itex]_{2n+1}[/itex]=F[itex]^{2}_{2n+1}[/itex]-1
F[itex]_{2(k+1)}[/itex]F[itex]_{2(k+1)+1}[/itex]=F[itex]^{2}_{2(k+1)+1}[/itex]-1

Since,

F[itex]_{2(k+1)}[/itex]=F[itex]_{2(k+1)+1}[/itex]-1

Then the equation becomes:

F[itex]_{2(k+1)+1}[/itex]F[itex]_{2(k+1)+1}[/itex]-1=F[itex]^{2}_{2(k+1)+1}[/itex]-1

Something doesn't sit right with me. I feel like this is incorrect. If it is, any and all help would be appreciated. Thank you.

Unit

It's quite a cute proof by induction, actually, if you can prove (or already know) that [itex]\sum_{k=1}^n F_k^2 = F_n F_{n+1}[/itex].

Let's assume [itex]F_1 = F_2 = 1[/itex] and [itex]F_{n+2} = F_{n+1} + F_n[/itex] for natural numbers n. Since the recursive relation refers to two lesser naturals, we should proceed with strong induction and two base cases.

Hence, for n = 1 we have:
[tex]\sum_{k=1}^{2} F_k F_{k+1} = F_1 F_2 + F_2 F_3 = 1 + 2 = 3 = 4 - 1 = 2^2 - 1 = F_3^2 - 1 = F_{2(1)+1}^2 - 1.[/tex]
For n = 2 we have:
[tex]\sum_{k=1}^{4} F_k F_{k+1} = 3 + F_3 F_4 + F_4 F_5 = 3 + 6 + 15 = 24 = 25 - 1 = 5^2 - 1 = F_5^2 - 1 = F_{2(2)+1}^2 - 1.[/tex]
Now suppose that [itex]\sum_{k=1}^{2j} F_k F_{k+1} = F_{2j+1}^2 - 1[/itex] for all [itex]j < n[/itex]. We want to show it's true for n itself. Break up the sum into recognizable parts:
[tex]\sum_{k=1}^{2n} F_k F_{k+1} = F_1 F_2 + \sum_{k=2}^{2n} F_k F_{k+1} = 1 + \sum_{k=2}^{2n} F_k (F_k + F_{k-1}) = 1 + \sum_{k=2}^{2n} F_k^2 + \sum_{k=2}^{2n} F_k F_{k-1}.[/tex]
The middle sum is 1 less than the identity at the start of my post. Note that [itex]F_k[/itex] and [itex]F_{k-1}[/itex] commute (luckily!) and so that last sum looks familiar, almost. Write it out in full, cut out a slice to which the induction hypothesis applies, and then deal with the rest.