How to Prove Fibonacci Squared Recurrence Relation

[alec_tronn]

Homework Statement

We were asked in a class discussion if we could try to figure out the recurrence relation of the Fibonacci squared sequence. I correctly figured that the equation was
F$$^{2}_{n}$$=2F$$^{2}_{n-1}$$ + 2F$$^{2}_{n-2}$$ - F$$^{2}_{n-3}$$

with F$$^{2}_{1}$$ = 0 and F$$^{2}_{2}$$ = 1 and F$$^{2}_{3}$$ = 1.

Now, our class homework is to prove it.

The Attempt at a Solution

My first instinct is proof by induction. So I start with:

Test the hypothesis with n=4 (since n=1,2,3 are given by definition).
F$$^{2}_{4}$$ = 2F$$^{2}_{3}$$ + 2F$$^{2}_{2}$$ - F$$^{2}_{1}$$
= 2 + 2 - 0
= 4, which agrees with original definition(because F$$^{1}_{4}$$ = 2, and thus F$$^{2}_{4}$$ = 4).

So, the formula holds for some arbitrary but fixed n (n being a member of the natural numbers).

Test n+1.
F$$^{2}_{n+1}$$ = (F$$^{1}_{n}$$ + F$$^{1}_{n-1}$$)^{2} (by definition. of Fib. Sequence)

=F$$^{2}_{n}$$ + 2 F$$^{1}_{n}$$ * F$$^{1}_{n-1}$$ + F$$^{2}_{n-1}$$ (by distribution)

= 2F$$^{2}_{n-1}$$ + 2F$$^{2}_{n-2}$$ - F$$^{2}_{n-3}$$ + 2 F$$^{1}_{n}$$ * F$$^{1}_{n-1}$$ + 2F$$^{2}_{n-2}$$ + 2F$$^{2}_{n-3}$$ - F$$^{2}_{n-4}$$ (by the induction hypothesis)

= 2F$$^{1}_{n-1}$$ * (F$$^{1}_{n}$$ + F$$^{1}_{n-1}$$) + 4F$$^{2}_{n-2}$$ + F$$^{2}_{n-3}$$ - F$$^{2}_{n-4}$$

=2F$$^{1}_{n-1}$$ * F$$^{1}_{n+1}$$ + 4F$$^{2}_{n-2}$$ + F$$^{2}_{n-3}$$ - F$$^{2}_{n-4}$$

That's where I'm stuck. I know (or think I know) that I'm supposed to end up with :
F$$^{2}_{n+1}$$ = 2F$$^{2}_{n}$$ + 2F$$^{2}_{n-1}$$ - F$$^{2}_{n-2}$$ and so for every n for which the formula is valid, the formula is also valid for n+1. By induction, the formula works for all of the natural numbers.

Could anyone help me figure out the part I'm stuck at?

 

[Vid]

F2n + 2(Fn)(Fn-1) + F2n-1
F2n + 2(Fn)(Fn - fn-2) + F2n-1
F2n +(2F2n) -(2fn-2*fn) + F2n-1
Use the induction hypothesis on the lone F2n
2F2n + (2F2n-1) + (2F2n-2) - (F2n-3) - 2(Fn*Fn-2) + F2n-1

Notice that the first two terms are the first two terms we are looking for. I'm going to leave those off and manipulate the last 4 terms into -Fn-2. The number of steps I used can probably be reduced under scrutiny, but I just did a rough sketch of this.

F2n-1 + 2F2n-2 - F2n-3 - 2( Fn-1 + Fn-2)*(Fn-2)
Notice that F2n-2 cancels after expanding the last term.
F2n-1 - 2Fn-1*Fn-2 - F2n-3
Write Fn-1 in the middle term as Fn-2 + Fn-3 then expand.

F2n-1 -2F2n-2 - 2Fn-2Fn-3 - F2n-3
Now write the first term as (Fn-2 + Fn-3)^2 and expand.
F2n-2 + 2Fn-2*Fn-3 +f2n-3 -2F2n-2 - 2Fn-2Fn-3 - F2n-3
Combining and canceling leaves just the term we are looking for -Fn-2
Combining that with the terms we dropped earlier gives us:
2F2n+ 2F2n-1 - F2n-2. QED

Sorry for being really messy, but I really didn't want to use a lot of energy typing this out.