How Can the Fibonacci Sequence Be Proved by Induction?

[williampb]

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

Prove that,

F_{1}F_{2}+F_{2}F_{3}+...+F_{2n}F_{2n+1}=F^{2}_{2n+1}-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_{2}+F_{4}+...+F_{2n}=F_{2n+1}-1

And then used that in the other proof.

For F_{2}+F_{4}+...+F_{2n}=F_{2n+1}-1

First,
For n=1 (base case)

F_{2(1)}=F_{2}=1

Then,

F_{2(k+1)}=F_{2(k+1)+1}-1+F_{2(k+1)}
=(F_{2k+3}+F_{2k+2})-1
=F_{2k+5}-1 = F_{2(k+2)+1}-1

Proving that F_{2k}=F_{2k+1}-1 for all k+1.

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

F_{2n}F_{2n+1}=F^{2}_{2n+1}-1
F_{2(k+1)}F_{2(k+1)+1}=F^{2}_{2(k+1)+1}-1

Since,

F_{2(k+1)}=F_{2(k+1)+1}-1

Then the equation becomes:

F_{2(k+1)+1}F_{2(k+1)+1}-1=F^{2}_{2(k+1)+1}-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]

I'm not sure how to prove this by straight induction

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

Let's assume F_1 = F_2 = 1 and F_{n+2} = F_{n+1} + F_n 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:
\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.
For n = 2 we have:
\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.
Now suppose that \sum_{k=1}^{2j} F_k F_{k+1} = F_{2j+1}^2 - 1 for all j < n. We want to show it's true for n itself. Break up the sum into recognizable parts:
\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}.
The middle sum is 1 less than the identity at the start of my post. Note that F_k and F_{k-1} 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.