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 it's just very long or a neat trick is required in the inductive step but for some odd reason it's not working out. Ideally I would like any suggestions for the inductive proof.
Solution 1:
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.
Solution 2:
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{equation} \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} \end{equation} Hence, \begin{equation} \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} \end{equation}
Solution 3:
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}