Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This one is easy if you use generating functions and Simpson multisection. –  ex0du5 Jul 20 '13 at 5:16
1  
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

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
+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{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}

share|improve this answer

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}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.