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 that: $$F_1F_2+F_2F_3+F_3F_4+\cdots+F_{2n-1}F_{2n}=F_{2n}^2$$

I set it up so:

$$F^2(2k) + F(2k+1)F(2k+2) = F^2(2k+2)$$

I've tried: $$F(2k)^2 + F(2k+1)*F(2k+2) = F(2k+2)*F(2k)+F(2k+2)*F(2k+1)$$ $$F(2k)^2 = F(2k+2)*F(2k)$$ $$F(2k+1)*F(2k) - F(2k)*F(2k-1) = F(2k)*F(2k)+F(2k)*F(2k+1)$$ $$-F(2k)*F(2k-1) = F(2k)^2$$

??? Is there something wrong with my initial induction hypothesis ?

share|improve this question
3  
Certainly you can write $F_{2k+1}=F_{2k}+F_{2k-1}$. Does that help? –  Ross Millikan Jan 24 '13 at 17:41
    
Why not prove it by induction? –  Ishan Banerjee Jan 24 '13 at 17:49
    
@IshanBanerjee Not sure what you mean. The remark that begins "I set it up so" indicates an argument by induction. –  Andres Caicedo Jan 24 '13 at 17:51
    
@RossMillikan thank you, I thought you could split it up like that but I just wasn't sure. I keep ending up with F(2k)^2 = -F(2k)*F(2k-1) –  draconisthe0ry Jan 24 '13 at 18:32
add comment

4 Answers

up vote 2 down vote accepted

There's a problem with what you're trying to show:

$$F^2(2k) + F(2k+1)F(2k+2) = F^2(2k+2)$$

Try writing out the summation explicitly for $n=1$ and $n=2$ and comparing it with what you have. You'll see that you forgot to include a term on the left-hand side.

I suspect this is the true reason why you've been unable to get the two sides to agree.

share|improve this answer
    
I see what you mean i'm getting $$1^2 + 2*3 = 7 = 3^2 = 9$$ Any hints on what is left out ? –  draconisthe0ry Jan 24 '13 at 19:08
    
@draconisthe0ry Sure, try to count the number of terms in the sum $F_1 F_2 + \ldots + F_{2n-1} F_{2n}$. You'll find that each time you increase $n$ by 1 you get two additional terms, not just one. This fact was somewhat obscured by the "dot dot dot" notation. –  Erick Wong Jan 24 '13 at 19:29
1  
F(2n-2)*F(2n-1)+F(2n-1)*F(2n) thanks @ErickWong you helped me out a lot! –  draconisthe0ry Jan 24 '13 at 20:21
add comment

We can avoid induction using Binet's Fibonacci Number Formula, $$F_n=\frac{a^n-b^n}{a-b}$$ where $a,b$ are the roots of $x^2-x-1=0\iff a+b=1,ab=-1$ also, $a^2-a-1=0$

$$F_rF_{r+1}=\frac{(a^r-b^r)}{(a-b)}\frac{(a^{r+1}-b^{r+1})}{(a-b)}=\frac{a^{2r+1}+b^{2r+1}-(ab)^r(a+b)}{(a-b)^2}$$ $$=\frac{a^{2r+1}+b^{2r+1}-(-1)^r}{(a-b)^2} \text{ as } ab=-1$$

So, $$(a-b)^2\sum_{m\le r\le m+n}F_rF_{r+1}$$ $$=\sum_{m\le r\le m+n}a^{2r+1}+\sum_{m\le r\le m+n}b^{2r+1}-\sum_{m\le r\le m+n}(-1)^r$$

$$=\frac{a^{2m+1}\{(a^2)^{n+1}-1\}}{a^2-1}+\frac{b^{2m+1}\{(b^2)^{n+1}-1\}}{b^2-1}-(-1)^m\sum_{0\le r\le n}(-1)^r$$

$$=a^{2(m+n+1)}+b^{2(m+n+1)}-(a^{2m}+b^{2m})-(-1)^m\sum_{0\le r\le n}(-1)^r$$ as $a^2-1=a$ as $a^2-a-1=0$

$$=(a^{m+n+1}-b^{m+n+1})^2+2(ab)^{m+n+1}-\{(a^m-b^m)^2+2(ab)^m\}-(-1)^m\sum_{0\le r\le n}(-1)^r$$

$$=(a^{m+n+1}-b^{m+n+1})^2-(a^m-b^m)^2-2(-1)^m\{(-1)^{n+1}-1\}-(-1)^m\sum_{0\le r\le n}(-1)^r$$

As the sum of even number of alternative positive negative real terms with same absolute value is $0,$ if $n$ is odd $=2k-1$(say),

$$(a-b)^2\sum_{m\le r\le m+2k-1}F_rF_{r+1}=(a^{m+2k}-b^{m+2k})^2-(a^m-b^m)^2$$

$$\implies \sum_{m\le r\le m+2k-1}F_rF_{r+1}=F_{m+2k}^2-F_m^2$$

$$m=0\implies \sum_{0\le r\le 2k-1}F_rF_{r+1}=F_{2k}^2-F_0^2=F_{2k}^2 \text{ as } F_0=0$$

$$\implies \sum_{1\le r\le 2k-1}F_rF_{r+1}=F_{2k}^2-F_0F_1=F_{2k}^2 \text{ as } F_0=0$$

share|improve this answer
add comment

Your setup is almost precisely what you'll need in the induction step for a proof by induction. You should instead have $$F^2(2k)+F(2k)F(2k+1)+F(2k+1)F(2k+2)=F^2(2k+2).$$ All that's left is to do the base step and work out the induction step details.

share|improve this answer
    
Agreed. He is very close. –  mez Jan 24 '13 at 18:00
1  
Not so precisely equal...Take a closer look. –  Erick Wong Jan 24 '13 at 18:43
    
@Erick: Thank you. I see now that the ellipsis hid a necessary term. –  Cameron Buie Jan 24 '13 at 20:03
add comment

$$F_{r+2}^2-F_r^2=(F_{r+2}-F_r)(F_{r+2}+F_r)=F_{r+1}(F_{r+2}+F_r)$$

So, $$F_{r+2}^2-F_r^2=F_{r+2}F_{r+1}+F_{r+1}F_r$$

We can utilize this fact to prove the required proposition without using induction.

Put $r=2n-2,2n-4,\cdots,4,2,0$ to get,

$$F_{2n}^2-F_{2n-2}^2=F_{2n}F_{2n-1}+F_{2n-1}F_{2n-2}$$ $$F_{2n-2}^2-F_{2n-4}^2=F_{2n-2}F_{2n-3}+F_{2n-3}F_{2n-4}$$

$$\cdots$$

$$F_{6}^2-F_{4}^2=F_{6}F_{5}+F_{5}F_{4}$$ $$F_{4}^2-F_{2}^2=F_{4}F_{3}+F_{3}F_{2}$$ $$F_{2}^2-F_{0}^2=F_{2}F_{1}+F_{1}F_{0}$$

Adding them we get, $$F_{2n}^2-F_0^2=\sum_{0\le m\le 2n-1}F_mF_{m+1}$$

But $$F_0=0\implies F_{2n}^2-F_0^2=F_{2n}^2$$ and $$ \sum_{0\le m\le 2n-1}F_mF_{m+1}=\sum_{1\le m\le 2n-1}F_mF_{m+1}+F_0F_1=\sum_{1\le m\le 2n-1}F_mF_{m+1}$$

So, $$F_{2n}^2=\sum_{1\le m\le 2n-1}F_mF_{m+1}$$

Similarly putting $r=2n-1,2n-3,\cdots,3,1$ and adding them we can derive $$\sum_{1\le m\le 2n}F_mF_{m+1}=F_{2n+1}^2-F_1^2=F_{2n+1}^2-1\text{ as }F_1=1$$

share|improve this answer
add comment

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.