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.