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?
 A: 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.
A: $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.
A: 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? 
A: 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?
A: 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. 

