1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to Prove Fibonacci Squared Recurrence Relation

  1. Jan 16, 2008 #1
    1. The problem statement, all variables and given/known data
    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[tex]^{2}_{n}[/tex]=2F[tex]^{2}_{n-1}[/tex] + 2F[tex]^{2}_{n-2}[/tex] - F[tex]^{2}_{n-3}[/tex]

    with F[tex]^{2}_{1}[/tex] = 0 and F[tex]^{2}_{2}[/tex] = 1 and F[tex]^{2}_{3}[/tex] = 1.

    Now, our class homework is to prove it.

    3. 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[tex]^{2}_{4}[/tex] = 2F[tex]^{2}_{3}[/tex] + 2F[tex]^{2}_{2}[/tex] - F[tex]^{2}_{1}[/tex]
    = 2 + 2 - 0
    = 4, which agrees with original definition(because F[tex]^{1}_{4}[/tex] = 2, and thus F[tex]^{2}_{4}[/tex] = 4).

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

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

    =F[tex]^{2}_{n}[/tex] + 2 F[tex]^{1}_{n}[/tex] * F[tex]^{1}_{n-1}[/tex] + F[tex]^{2}_{n-1}[/tex] (by distribution)

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

    = 2F[tex]^{1}_{n-1}[/tex] * (F[tex]^{1}_{n}[/tex] + F[tex]^{1}_{n-1}[/tex]) + 4F[tex]^{2}_{n-2}[/tex] + F[tex]^{2}_{n-3}[/tex] - F[tex]^{2}_{n-4}[/tex]

    =2F[tex]^{1}_{n-1}[/tex] * F[tex]^{1}_{n+1}[/tex] + 4F[tex]^{2}_{n-2}[/tex] + F[tex]^{2}_{n-3}[/tex] - F[tex]^{2}_{n-4}[/tex]

    That's where I'm stuck. I know (or think I know) that I'm supposed to end up with :
    F[tex]^{2}_{n+1}[/tex] = 2F[tex]^{2}_{n}[/tex] + 2F[tex]^{2}_{n-1}[/tex] - F[tex]^{2}_{n-2}[/tex] 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?
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Jan 16, 2008 #2


    User Avatar

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook