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.