# Fibonacci Cubes: $F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$

Prove

$$F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$$

I've tried induction, either its just very long or a neat trick is required in the inductive step but for some odd reason its not working out. Ideally I would like any suggestions for the inductive proof, thanks.

-
This one is easy if you use generating functions and Simpson multisection. – ex0du5 Jul 20 '13 at 5:16
What contest, please? – Gerry Myerson Jul 20 '13 at 6:01
I've changed (number-theory) to (elementary-number-theory); I think this is a more suitable tag. – Martin Sleziak Jul 20 '13 at 9:32
This is in a book which Im using to get myself up to scratch with Putnam competitors, despite being in the UK. Generating functions is something I need to read soon but Simpson multisection, I can't find anything on that? – WhizKid Jul 20 '13 at 14:35
@ex0du5 I believe that the last WhizKid's comment was meant for you. WhizKid: Links to some basic info about how to reply to a specific person in comments can be found here. Maybe posts tagged comment-replies on meta might be interesting, too. – Martin Sleziak Jul 23 '13 at 7:19

Here you'll sort of see my thought process; hopefully it helps.

First you need to define the Fibonacci sequence as $F_1 = 1, F_2 = 1, F_{n+1} = F_{n} + F_{n-1}$ for this to hold. If you somehow want to use induction, you need to write $F_{n+1}$ with the recurrence relation, whence $S = F_{n}^3 - F_{n-1}^3 + (F_{n}+F_{n-1})^3 = F_{n}^3 - F_{n-1}^3 + 3F_n^2 F_{n-1} + 3F_n F_{n-1}^2 + F_{n}^3 + F_{n-1}^3.$

Writing $-F_{n-2} = F_{n-1} - F_{n}$ gives $-F_{n-2}^3 = F_{n-1}^3 - F_{n}^3 + 3F_{n}^2F_{n-1} - 3F_n F_{n-1}^2$ and thus, $S = F_n^3 + F_{n-1}^3 - F_{n-2}^3 + 2(F_n^3 - F_{n-1}^3 + 3F_n F_{n-1}^2) = F_{3n-3}+2(F_n^3 - F_{n-1}^3 + 3F_n F_{n-1}^2).$

To make it clear what exactly we need, if $S = F_{3n},$ then $S = F_{3n-1} + F_{3n-2} = 2F_{3n-2} + F_{3n-3},$ so in fact we want to prove that $F_{n}^3 + 3F_{n}F_{n-1}^2 - F_{n-1}^3 = F_{3n-2}.$ Looking back at our first equation for $S,$ this means we also need $F_{n}^3 + 3F_{n}^2F_{n-1} + F_{n-1}^3 = F_{3n-1}.$

Claim: $F_{n}^3 + 3F_{n}F_{n-1}^2 - F_{n-1}^3 = F_{3n-2}$ and $F_{n}^3 + 3F_{n}^2F_{n-1} + F_{n-1}^3 = F_{3n-1}.$

Proof: The base cases are easy to check. We proceed by double induction. That is, assume the claim holds for some $n.$ Then for $n+1,$ we have \begin{align*} F_{n+1}^3 + 3F_{n+1}F_{n}^2 - F_{n}^3& = (F_n + F_{n-1})^3 + 3F_n^3 + 3F_n^2 F_{n-1} - F_n^3 \\&= \underbrace{F_{n}^3 + 3F_{n}^2 F_{n-1}} + 3F_{n}F_{n-1}^2 + \underbrace{F_{n-1}^3} + 2F_{n}^3 + 3F_{n}^2F_{n-1} \\&= F_{3n-1} + 2F_{n}^3 + 3F_{n}^2F_{n-1} + 3F_{n}F^2_{n-1}\\ &= F_{3n-1} + (F_n^3 + 3F_{n}^2F_{n-1} + F_{n-1}^3) + (F_{n}^3+3F_{n}F_{n-1}^2 - F_{n-1}^3)\\ &=F_{3n-1} + F_{3n-1} + F_{3n-2} = F_{3n-1} + F_{3n} = F_{3n+1} = F_{3(n+1) - 2}. \end{align*}

Similarly, one shows that $F_{n+1}^3 + 3F_{n+1}^2 F_n + F_{n}^3 = F_{3(n+1) - 1},$ whence we are done.

tl;dr: Abuse the Fibonacci recurrence relation and the inductive hypotheses.

-
Thanks, I was particularly looking to do the inductive proof, I guess I should of just kept with it until it dropped it. – WhizKid Jul 20 '13 at 14:40

By expanding $(\frac {\phi^n - \psi^n}{\phi- \psi})^3$, you obtain that $F_n^3$ is a linear combination of $\phi^{3n}, (\psi \phi^2)^n, (\psi^2 \phi)^n, \psi^{3n}$, and so is the whole LHS. In particular, the LHS satisfies a linear recurrence relation of order $4$.

The RHS is a linear combination of $\phi^{3n}$ and $\psi^{3n}$, so it satisfies the same linear recurrence relation.

Thus it is enough to check that the equality is true for the first $4$ terms.

If you wish you can compute the exact linear recurrence relation by computing the polynomial $(X-\phi^3)(X-\psi\phi^2)(X-\psi^2\phi)(X-\psi^3)$, though it is not necessary.

-
+1. This is a beautiful proof, in the style of the $A=B$ book (math.upenn.edu/~wilf/AeqB.html) – ShreevatsaR Jul 20 '13 at 9:33
Very elegant, is there any other question(s) you have in mind that work on a similar technique (possibly the inspiration that led to this idea), thanks. – WhizKid Jul 20 '13 at 14:38

Use the algebraic identity $$(a-b)^3+a^3-b^3=(a-b)\left(2(a-b)^2+3ab\right)$$ and use theFibonacci sequence relation $F_{n+1}=F_n+F_{n-1}$ to get $$F_n^3+F_{n+1}^3-F_{n-1}^3=F _n\left(2F_n^2+3F_{n+1}F_{n-1}\right)$$ Now, by Binet's formula $$F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$$ where $\alpha=\frac{1+\sqrt{5}}{2}$, $\beta=\frac{1-\sqrt{5}}{2}$. Then, we get, $$\begin{split} F_{n+1}F_{n-1}= & \frac{(\alpha^{n+1}-\beta^{n+1})(\alpha^{n-1}-\beta^{n-1})}{(\alpha-\beta)^2}\\ \ =& \frac{\alpha^{2n}+\beta^{2n}-\alpha^{n-1}\beta^{n-1}(\alpha^2+\beta^2)}{5}\ \mbox{(Since }\alpha-\beta=\sqrt{5})\\ \ =& \frac{\alpha^{2n}+\beta^{2n}+3\alpha^{n}\beta^{n}}{5}\ \mbox{(Since }\alpha\beta=-1,\ \alpha^2+\beta^2=3)\\ \end{split}$$ Hence, $$\begin{split} F_n^3+F_{n+1}^3-F_{n-1}^3=& F _n\left(2F_n^2+3F_{n+1}F_{n-1}\right)\\ \ =& \frac{\alpha^n-\beta^n}{\alpha-\beta}\frac{\left(2(\alpha^{2n}+\beta^{2n}-2\alpha^n\beta^n)+3(\alpha^{2n}+\beta^{2n}+3\alpha^n\beta^n)\right)}{5}\\ \ =&5\frac{(\alpha^n-\beta^n)(\alpha^{2n}+\beta^{2n}+\alpha^n\beta^n)}{5(\alpha-\beta)}\\ \ =&\frac{\alpha^{3n}-\beta^{3n}}{\alpha-\beta}\\ \ =& F_{3n}\hspace{6cm} \Box \end{split}$$

-

Maybe you could start by showing that $$F_{a+b}=F_aF_{b+1}+F_{a-1}F_b. \tag{1}$$ IIRC this is sometimes called convolution identity. One possible derivation of this identity is given on Wikipedia. (I'll add also a link to the recent revision of the Wikipedia article - just in the case it changes in the future.)
See also this post: Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$
Very similar identity is shown in this post: Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers

Using (1) for $a=b=n$ you get $$F_{2n}=F_n(F_{n+1}+F_{n-1})$$ Using (1) for $a=n+1$ and $b=n$ you get $$F_{2n+1}=F_{n+1}^2+F_n^2.$$

Now if we use (1) for $a=n$ and $b=2n$, we obtain \begin{align} F_{3n}&=F_nF_{2n+1}+F_{n-1}F_{2n}=\\ &=F_n(F_{n+1}^2+F_n^2)+F_{n-1}F_n(F_{n+1}+F_{n-1})=\\ &=F_n^3+F_nF_{n+1}^2+F_{n-1}(F_{n+1}-F_{n-1})(F_{n+1}+F_{n-1})=\\ &=F_n^3+F_nF_{n+1}^2+F_{n-1}(F_{n+1}^2-F_{n-1}^2)=\\ &=F_n^3+F_nF_{n+1}^2+F_{n-1}F_{n+1}^2-F_{n-1}^3=\\ &=F_n^3+(F_n+F_{n-1})F_{n+1}^2-F_{n-1}^3=\\ &=F_n^3+F_{n+1}^3-F_{n-1}^3 \end{align}

-