Show $f_{2n} = f_{n}^2 + 2f_{n-1}f_{n}$ where $f_n$ is the $n^{th}$ fibonacci number Note that for this problem $f_0 = 0, f_1 = 1, f_n = f_{n-1} + f_{n-2}$
My work so far is to write down the base case and the induction hypothesis. Then the problem becomes showing:
$f_{2n} = f_{n}^2 + 2f_{n-1}f_{n} \implies f_{2(n+1)} = f_{n+1}^2 + 2f_{n}f_{n+1}$
I've done this so far but beyond here I'm stuck. I don't know what to do with $f_{2n+1}$
$f_{2(n+1)} = f_{2n + 1} + f_{2n} = f_{2n+1} + f_n^2 + 2f_{n-1}f_{n} $
 A: (Not the appropriate approach for a class exercise, in most cases, but it is worth seeing it.)
The linear algebra approach.
Prove by induction that:
$$\begin{pmatrix}F_{n}&F_{n+1}\\
F_{n+1}&F_{n+2}\end{pmatrix}=\begin{pmatrix}0&1\\1&1\end{pmatrix}^n\tag{1}$$
Then use $$A^{2n}=\left(A^n\right)^2$$ where $A=\begin{pmatrix}0&1\\1&1\end{pmatrix}$.

Formula (1) lets you quickly see that $F_{n}F_{n+2}-F_{n+1}^2=(-1)^n$, since these are the determinants of both sides of (1).
Also you see that the eigenvalues of $A$ are $\frac{1\pm \sqrt{5}}{2}$. Diagonalizing $A$ gives you de Moivre's formula for the Fibonacci numbers.
A: How about using induction to prove that
$$f_{m+n}=f_{m-1}\,f_n+f_m\,f_{n+1}\,?$$
Plugging $m:=n$ should solve the problem.

You can also use induction to prove that $f_n$ is the number of binary sequences of length $n-2$ such that the number $1$ does not appear consecutively (we shall call such sequences good).  Then, $f_{2n}$ counts good sequences of length $2n-2$.  Split this good sequence into two halves.  If the end of the first half and the beginning of the second half are both $0$, then there are $f_n^2$ such good sequences.  If the end of the first half is $1$ and the beginning of the second half is $0$, then there are $f_nf_{n-1}$ such good sequences.  If the end of the first half is $0$ and the beginning of the second half is $1$, then there are also $f_nf_{n-1}$ such sequences.  (Well, this combinatorial argument can also be used to prove the identity for $f_{m+n}$ above too.)
A: Every second term in the Fibonacci sequence satisfies the recurrence relation $F_{2n+2}=3 F_{2n} -F_{2n-2}$. Now use induction
\begin{eqnarray*}
F_{2n+2}&=&3 F_{2n} -F_{2n-2} \\
&=&3(F_n^2+2F_{n-1}F_n) - (F_{n-1}^2+2 F_{n-2} F_{n-1}) \\
&=&3F_n^2+6F_{n-1}F_n - F_{n-1}^2-2  F_{n-1}(F_n-F_{n-1}) \\
&=&3F_n^2+4F_n(F_{n+1}-F_n) +(  F_{n+1} - F_{n})^2 \\
&=&F_{n+1}^2 +2F_n F_{n+1}.
\end{eqnarray*}
A: Let $S$ be the shift operator on sequences; that is,  $Sa_n=a_{n+1}$. Then,
$$
S^ka_n=a_{n+k}\tag{1}
$$
Thus, for the Fibonacci Sequence,
$$
\left(S^2-S-1\right)F_n=0\tag{2}
$$
Using $(2)$, we can derive by induction
$$
S^kF_n=\left(F_kS+F_{k-1}\right)F_n\tag{3}
$$
Setting $k=n$ in $(3)$ yields
$$
\begin{align}
F_{2n}
&=F_nF_{n+1}+F_{n-1}F_n\\
&=F_n(F_n+F_{n-1})+F_{n-1}F_n\\
&=F_n^2+2F_nF_{n-1}\tag{4}
\end{align}
$$

Inductive Proof of $\boldsymbol{(3)}$
Initial condition: $SF_n=(\overbrace{1}^{F_1}S+\overbrace{0}^{F_0})F_n$
Suppose True for $S^kF_n$, then
$$
\begin{align}
S^{k+1}F_n
&=S\left(S^k\right)F_n\\
&=S\left(F_kS+F_{k-1}\right)F_n\\
&=\left(F_k(S+1)+F_{k-1}S\right)F_n\\[1pt]
&=\left(F_{k+1}S+F_k\right)F_n\tag{5}
\end{align}
$$
Thus, it's true for $S^{k+1}F_n$.
A: Alternatively, using:
$$f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right),$$
we get:
$$f_{2n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{2n}-\left(\frac{1-\sqrt{5}}{2}\right)^{2n}\right),$$
$$f_n^2=\frac15 \left(\left(\frac{1+\sqrt{5}}{2}\right)^{2n}-2(-1)^n+\left(\frac{1-\sqrt{5}}{2}\right)^{2n}\right),$$
$$2f_{n-1}f_n=2\cdot \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right) \cdot \frac{1}{\sqrt{5}} \left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)=$$
$$\frac{1}{5}\left((\sqrt{5}-1)\left(\frac{1+\sqrt{5}}{2}\right)^{2n}+2(-1)^n-(\sqrt{5}+1)\left(\frac{1-\sqrt{5}}{2}\right)^{2n}\right).$$
Indeed:
$$2f_{n-1}f_n+f_n^2=f_{2n}.$$
