# Fibonacci Proof

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 ?

-
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) –  O.rka Jan 24 '13 at 18:32

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.

-
I see what you mean i'm getting $$1^2 + 2*3 = 7 = 3^2 = 9$$ Any hints on what is left out ? –  O.rka 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
F(2n-2)*F(2n-1)+F(2n-1)*F(2n) thanks @ErickWong you helped me out a lot! –  O.rka Jan 24 '13 at 20:21

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$$

-

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.

-
Agreed. He is very close. –  mez Jan 24 '13 at 18:00
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

$$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$$

-

Prove $F_1F_2 + F_2F_3 + F_3F_4 + \cdots + F_{2n-1}F_{2n} = F^2_{2n}$.

Base case $n = 1 \Longrightarrow F_1F_2 = F_{2(1)} = 1$ is true

Assume true for all $m \in \Bbb{N}: m \leq n$. We prove $F_1F_2 + F_2F_3 + F_3F_4 + \cdots + F_{2n+1}F_{2n+2} = F^2_{2(n+1)}$.

On the LHS we get $F_{2n}^2 + F_{2n}F_{2n+1} + F_{2n+1}F_{2n+2} = F^2_{2n} + F_{2n}F_{2n+1} + F_{2n+1}(F_{2n} + F_{2n+1})$ but this all simplifies down to $$(F_{2n}+F_{2n+1})^2$$

-