6
$\begingroup$

I am trying to solve the following exercise:

Let $f_1=1$, $f_2=1$, $f_{n+1}=f_n+f_{n-1}$, where $n\in\mathbb{N}$. Show that $f_{2n+1}=f_{n+1}^2+f_n^2$.

I have not had much progress, but this is what I have managed to observe:

$\sum_{k=1}^nf_{2k}=f_{2n+1}-1.$

However, this is not of much help when trying to show the above.

Also, $f_{n+1}^2=(f_n+f_{n-1})^2=f_n^2+2f_{n+1}+f_{n-1}^2$, and $f_n^2=(f_{n-1}+f_{n-2})^2=f_{n-1}^2+2f_n+f_{n-2}^2$. But when I add these, I do not get anything that resembles the LHS above.

Do you guys have any ideas?

  • 0
    Yes, this question is the special-case $n = m+1$ of the general addition formula in the linked dupe, and the answers are special cases of answers there.2012-04-28

5 Answers 5

11

This result, and others like it, is most easily shown using matrices. First, prove to yourself by induction that $\left(\begin{array}{cc}1&1 \\ 1&0\end{array}\right)^n = \left(\begin{array}{cc}f_{n+1}&f_n \\ f_n&f_{n-1}\end{array}\right).$ (We choose $f_0 = 0$, of course.) Let $M = \left(\begin{array}{cc}1&1 \\ 1&0\end{array}\right)$. Then $M^{2n} = M^n M^n$ implies $\begin{eqnarray*} \left(\begin{array}{cc}f_{2n+1}&f_{2n} \\ f_{2n}&f_{2n-1}\end{array}\right) &=& \left(\begin{array}{cc}f_{n+1}&f_n \\ f_n&f_{n-1}\end{array}\right)^2 \\ &=& \left( \begin{array}{cc} f_{n+1}^2 + f_n^2 & f_{n+1}f_n + f_n f_{n-1} \\ \cdots & \cdots \end{array}\right), \end{eqnarray*}$ where we have left out entries that give nothing new. Therefore, we immediately have $f_{2n+1} = f_{n+1}^2 + f_n^2.$ We also get $f_{2n} = f_n(f_{n+1} + f_{n-1}) = f_n(f_n + 2f_{n-1})$ for free.

This is the Fibonacci sequence, about which much is known.

I recommend playing around with this technique. For example, what does $M^m M^n = M^{m+n}$ imply about the sequence?

  • 0
    Note that this is a special-case of answers in the [linked duplicate above.](http://math.stackexchange.com/questions/11477/showing-that-an-equation-holds-true-with-a-fibonacci-sequence-f-nm-f-n-1)2012-04-28
4

There's surely a more beautiful proof, but you can prove your formula by induction if you prove the formula $ f_{2n} = f_{n+1}^2 - f_{n-1}^2 $ simultaneously.

  • 0
    Sorry for the comment proliferation. By "one copy" I mean write $2f_{n+1}^2 = f_{n+1}^2 + f_{n+1}^2$ and expand only one of those two summands.2012-04-25
3

$f_{2n+1} = f_{2n} + f_{2n-1}$

Using the formula again on $f_{2n}$,

$f_{2n+1} = 2f_{2n-1} + f_{2n-2}$

Now using it on $f_{2n-1}$,

$f_{2n+1} = 3f_{2n-1} + 2f_{2n-2}$

Suppose after iterating this process i times, we have

$f_{2n+1} = a_if_{2n+1-i} + b_if_{2n-i}$

Then after the next iteration we will have

$f_{2n+1} = (a_i+b_i)f_{2n-i} + a_if_{2n-i}$

In other words, $b_{i+1} = a_i$ and $a_{i+1} = a_i + b_i$.

So $a_i = b_{i+1}$ and $b_{i+2} = b_{i+1} + b_i$. Since $b_1 = b_2 = 1$, $b_i = f_i$.

Moreover, after i iteration of the process we have

$f_{2n+1} = b_{i+1}f_{2n+1-i} + b_if_{2n-i} = f_{i+1}f_{2n+1-i} + f_if_{2n-i}$

Now just set i = n, and you get the result.

1

In an effort to find a more beautiful proof, we would try looking at this geometrically. By looking at the golden rectangle in terms of area, we can deduce that $f_{n+1}^2+f_{n}^2=f_{n+2}f_{n+1}-f_{n}f_{n-1}$. From the golden rectangle we can also get: $f_{n+1}^2-f_{n-1}^2=f_{n+2}f_{n+1}+f_{n}f_{n+1}$. Perhaps something pretty can come of these?

0

Here's a geometrical approach that I posted as an answer to a question that was closed as a duplicate of this one. I'll repost it here, I hope that's ok.

First create a rectangle with length $F_{2n+1}$ and height $F_1 = 1$. Then cut this up into two rectangles with sizes $F_{2n} \times F_2$ (i.e. $F_{2n} \times 1$) and $F_{2n-1} \times F_1$ (i.e. $F_{2n-1} \times 1$). Put the latter under the former.

Then cut the resulting figure into rectangles with sizes $F_{2n-1} \times F_3$ and $F_{2n-2} \times F_2$. Again, put the latter under the former.

Now cut the resulting figure into rectangles $F_{2n-2} \times F_4$ and $F_{2n-3} \times F_3$ and put the latter under the former.

Eventually, after $n-1$ steps you will get a figure built up from two squares with sizes $F_{n+1}^2$ and $F_n^2$.

See below figure for an example with $n=6$, i.e. $F_{2n+1} = F_{13} = 233$. The first line is the $F_{13} \times F_1$ rectangle. After $n-1=5$ steps you will reach a figure which can be divided into $F_7^2$ and $F_6^2$ as desired.

enter image description here