# Showing that $f_{2n+1}=f_{n+1}^2+f_n^2$.

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?

-
–  Aryabhata Apr 25 '12 at 6:30
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. –  Bill Dubuque Apr 28 '12 at 2:51

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?

-
I like this approach a lot. Thanks! –  Josué Apr 25 '12 at 13:49
@JosuéMolina: Glad to help. One last example, notice that by taking the determinant of each side of the first equation we get Cassini's identity, $f_{n+1}f_{n-1} - f_n^2 = (-)^n$. –  user26872 Apr 25 '12 at 14:57
There is actually an interesting article about this interpretation of the Fibonacci sequence in this month's Mathematics Magazine for those who are curious about some more of its utility in proofs. –  Alexander L Apr 26 '12 at 3:17
Note that this is a special-case of answers in the linked duplicate above. –  Bill Dubuque Apr 28 '12 at 2:49

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.

-
How did you obtain that? Did you know it beforehand? –  Josué Apr 25 '12 at 5:46
No. I reasoned what $f_{2n}$ had to be if the formula you were asking me to prove were true by using $f_{2n + 1} = f_{2n} + f_{2n-1}$ and writing $2n - 1 = 2(n-1) + 1$. –  user29743 Apr 25 '12 at 5:48
Just a remark - when you go to write out the induction, the odd case isn't bad, but the even case is equivalent to the formula $2f_{n+1}^2 + f_n^2 - f_{n-1}^2 = f_{n+2}^2 - f_n^2$ which follows from expanding out $f_{n+2}$ and one (but not both) copy of $f_{n+1}$ using the recurrence. –  user29743 Apr 25 '12 at 6:04
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. –  user29743 Apr 25 '12 at 6:12

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

-

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?

-

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.

-