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

Solution 1:

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?

Solution 2:

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.

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