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. 
 A: 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.
A: 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} 
A: 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}
A: 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.
