Homework Help: Fibonacci Cubed Recurrence Relation

1. Mar 2, 2008

alec_tronn

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$$_{n}$$ = 3G$$_{n-1}$$ + 6G$$_{n-2}$$ - 3G$$_{n-3}$$ - G$$_{n-4}$$

(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$$_{n+1}$$ = G$$_{n}$$ + F$$_{n}$$*F$$_{n+1}$$*F$$_{n-1}$$ + G$$_{n-1}$$

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. Mar 2, 2008

jhicks

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
3. Mar 3, 2008

alec_tronn

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!

4. Mar 3, 2008

jhicks

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 $$H_n$$ denote the nth fibonacci square

$$H_n = (F_n)^2 = (F_{n-1}+F_{n-2})^2 = H_{n-1} + H_{n-2} + 2F_{n-1}F_{n-2}$$

Using the substitution selectively that $$F_{n-1} = F_{n-2} + F_{n-3}$$, $$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}$$.

The trick is then to add and subtract $$(F_{n-3})^2$$:

$$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}$$.

Last edited: Mar 3, 2008