19
$\begingroup$

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?

$\endgroup$

5 Answers 5

31
$\begingroup$

This identity is clear from the following diagram:

enter image description here

(imagine here a generalized picture with $F_i$ notation)

The area of the rectangle is obviously

$$F_n(F_{n}+F_{n-1})=F_nF_{n+1}$$

On the other hand, since the area of a square is x^2, it is obviously:

$$F_1^2+F_2^2+\dots+F_n^2$$

Therefore:

$$F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$$


You can even convert this graphical proof to an inductive proof - your inductive step would consist of adding a square $F_{n+1} * F_{n+1}$.

$\endgroup$
1
  • 2
    $\begingroup$ Beautiful answer! $\endgroup$ Jan 19, 2017 at 4:29
18
$\begingroup$

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:

$$\begin{align*} 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)\end{align*} $$

$\endgroup$
1
  • $\begingroup$ I wanted to ask due to my own stupidity, but but if the inductive assumption is an assumption how do we know the subsequent derivation holds? $\endgroup$ May 21, 2023 at 13:18
7
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ See also here. $\endgroup$ Aug 9, 2013 at 4:51
  • 1
    $\begingroup$ @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. $\endgroup$
    – coffeemath
    Aug 9, 2013 at 5:55
7
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Nice case of a telescoping sum, once it was rearranged. +1 $\endgroup$
    – coffeemath
    Jul 13, 2013 at 6:46
  • $\begingroup$ @coffeemath, thanks for pointing out the term $\endgroup$ Jul 13, 2013 at 9:40
  • $\begingroup$ How come you can set F0 = 0 in here? $\endgroup$ May 21, 2023 at 13:07
0
$\begingroup$

Since $F_k=F_{k+1}-F_{k-1}$ for all $k\geq 1$, we have that $$\sum_{k=1}^n F_k^2=\sum_{k=1}^n F_k(F_{k+1}-F_{k-1})$$ $$\implies\sum_{k=1}^n F_k^2=\sum_{k=1}^n F_kF_{k+1}-\sum_{k=1}^n F_kF_{k-1}$$ But since $F_0=0$, we have $S=\sum_{k=1}^n F_kF_{k-1}=\sum_{k=1}^{n-1} F_{k+1}F_{k}$. Then $\sum_{k=1}^n F_kF_{k+1}=S+F_nF_{n+1}$ and finally we get, $$\sum_{k=1}^n F_k^2=F_nF_{n+1}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .