Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fibonacci Cubed Recurrence Relation

  1. Mar 2, 2008 #1
    1. The problem statement, all variables and given/known data
    Find and prove the recurrence relation for the Fibonacci cubed sequence.

    2. Relevant equations
    By observation (blankly staring at the sequence for an hour) I've decided that the recurrence relation is G[tex]_{n}[/tex] = 3G[tex]_{n-1}[/tex] + 6G[tex]_{n-2}[/tex] - 3G[tex]_{n-3}[/tex] - G[tex]_{n-4}[/tex]

    (where G is Fibonacci cubed)

    3. The attempt at a solution
    My attempt was going to be to prove by induction, but for the n+1 case, I got:
    G[tex]_{n+1}[/tex] = G[tex]_{n}[/tex] + F[tex]_{n}[/tex]*F[tex]_{n+1}[/tex]*F[tex]_{n-1}[/tex] + G[tex]_{n-1}[/tex]

    Is there an identity that could get me further? Is there a different method anyone could suggest? Is there anything I can do at all?

    edit: all that superscript is supposed to be subscript... I'm not sure what happened...
    Last edited: Mar 2, 2008
  2. jcsd
  3. Mar 2, 2008 #2
    I fear your question is esoteric enough that help will be hard to find without a definition of "fibonacci cubed" (or more specifically the sequence, since you do not know the relation). It doesn't seem like a hard question - just an obscure one. (Amusingly enough the first google result for "fibonacci cubed" is this thread!)

    My guess is LaTeX fouled up because you didn't properly anchor the subscripts to something.
    Last edited: Mar 3, 2008
  4. Mar 3, 2008 #3
    Since the Fibonacci sequence is 0,1,1,2,3,5,8,... the Fibonacci Cubed sequence is 0,1,1,8,27,125,512... it's just cubing each element of the Fibonacci sequence. Upon further research, I found that that rule was found and proven by Zeitlin and Parker and published in the Fibonacci Quarterly in 1963... not that I have access to that publication, but if any of you do, or find out how it was done, or have any advice, it'd be greatly appreciated!
  5. Mar 3, 2008 #4
    I think an easier approach would be to solve a simpler case first. Have you tried deriving the equation for a "fibonacci square" sequence? I assume a similar approach would follow for your case:

    Let [tex]H_n[/tex] denote the nth fibonacci square

    [tex]H_n = (F_n)^2 = (F_{n-1}+F_{n-2})^2 = H_{n-1} + H_{n-2} + 2F_{n-1}F_{n-2}[/tex]

    Using the substitution selectively that [tex]F_{n-1} = F_{n-2} + F_{n-3}[/tex], [tex]H_{n-1}+H_{n-2}+2F_{n-1}F_{n-2}=H_{n-1}+H_{n-2}+2(F_{n-2}+F_{n-3})F_{n-2} = H_{n-1}+H_{n-2}+2(F_{n-2})^2 + 2F_{n-2}F_{n-3}[/tex].

    The trick is then to add and subtract [tex](F_{n-3})^2[/tex]:

    [tex]H_{n-1}+2H_{n-2}+(F_{n-2})^2 + 2F_{n-2}F_{n-3} + (F_{n-3})^2 - (F_{n-3})^2 = 2H_{n-1}+2H_{n-2}-H_{n-3}[/tex].
    Last edited: Mar 3, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook