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.

The definition of a Fibonacci number is as follows:

$$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$

Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. $$F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$$

I am pretty sure I should use weak induction to solve this. My professor got me used to solving it in the following format, which I would like to use because it help me map everything out...

This is what I have so far:

Base Case: Solve for $F_0$ and $F_1$ for the following function: $F_nF_{n+1}$.

Inductive Hypothesis: What I need to show: I need to show $F_{n+1}F_{n+1+1}$ will satisfy the given property. Proof Proper: (didn't get to it yet)

Any intro. tips and pointers?

share|improve this question

3 Answers 3

The inductive assumption for $n$ is

$$F(1)^2+\ldots+F(n)^2=F(n)F(n+1)$$.

Using this, the $n+1$ case is:

$$F(1)^2+\ldots +F(n)^2+F(n+1)^2=F(n)F(n+1)+F(n+1)^2=F(n+1)(F(n)+F(n+1))=F(n+1)F(n+2)$$

share|improve this answer

Following can be another way:

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

Putting $r=1,2,3,\cdots,n-1,n$ and adding we get

$$F_nF_{n+1}=\sum_{1\le r\le n }F_r^2+F_0F_1=\sum_{1\le r\le n }F_r^2$$ as $F_0=0$

share|improve this answer
    
Nice case of a telescoping sum, once it was rearranged. +1 –  coffeemath Jul 13 '13 at 6:46
    
@coffeemath, thanks for pointing out the term –  lab bhattacharjee Jul 13 '13 at 9:40

A nice pictorial proof can be obtained by first placing two 1x1 squares horizontally (so that's $F_1+F_2$ so far), then a 2x2 square on top of those (so now we have a 2x3 rectangle containing $F_1^2,F_2^2,F_3^2$), then a 3x3 rectangle to the right of the rectangle we now have (so now it has size 3x5), and so on. After placing the $n$th square in this diagram, the rectangle will have dimensions $F_n \times F_{n+1}$, and the total number of unit squares inside it will be the sum of the squares of the first $n$ Fibonacci numbers.

share|improve this answer
1  
See also here. –  Martin Sleziak Aug 9 '13 at 4:51
    
@MartinSleziak The link in your comment gives the same thing, but with the Fibonacci squares winding around in a spiral, for a nice looking diagram. In my version above, the squares are placed alternately horizontal and vertical, so that the first 1x1 square winds up at the lower left of each of the big rectangles formed. –  coffeemath Aug 9 '13 at 5:55

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.