Proving a Fibonacci identity: $F_{2n} = F_n (F_{n+1} + F_{n-1})$ $$
F_{2n} = F_n (F_{n+1} + F_{n-1})
$$
I'm so stuck. I've used the definition of Fibonacci to change $F_{2n+2}$ into $F_{2n+1} + F_{2n}$. Can't use other properties, only the inductive hypothesis and the definition of Fibonacci.
 A: Here is a solution which includes only basic combinatorial arguments:
A famous combinatorial interpretation of the Fibonacci Numbers (which is also easy to prove inductively) is the following:
$F_n$ is the number of possibilities to walk up $n-1$ stairs where every step is either one, either two stairs.
Now, we count the number of possible walks on $(2n-1)$ stairs in two different manners.
On the one side, this is (by the above interpretation) equal to $F_{2n}$.
On the other side, we can distinguish two cases:
If such a walk contains a step onto the $n$-th stair, there are clearly $F_nF_{n+1}$ possibilities.
If it does not contain that step, it must contain the $(n-1)$-th and the $(n+1)$t-h stair, i.e. there are $F_{n-1} \cdot F_n$ possibilities.
Thus, the total number of possible walks is
$$F_{2n}=F_n(F_{n-1}+F_{n+1})$$
which is exactly the desired identity.
A: This follows from the matrix formulation, which is well worth knowing and easily proved:
$$
\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=
\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}
$$
Just compare
$$
\begin{pmatrix}1&1\\1&0\end{pmatrix}^{2n}=
\begin{pmatrix}*&F_{2n}\\*&*\end{pmatrix}
$$
with
$$
\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}^2=
\begin{pmatrix}*&\cdots\\*&*\end{pmatrix}
$$
A: (Late but after a duplicate was asked)
If you also assert something like $F_{2n-1} = F_n^2+F_{n-1}^2$ as well, then you can prove the two together by induction over $n$, showing:

*

*$F_{2k+1}=F_{2k-1}+F_{2k} =F_k^2+F_{k-1}^2 +F_kF_{k-1}+F_kF_{k+1} = F_k^2+F_{k+1}^2$

*$F_{2k+2}=F_{2k}+F_{2k+1} =F_kF_{k+1} +F_kF_{k-1}+F_k^2+F_{k+1}^2= F_kF_{k+1}+F_{k+2}F_{k+1}$
as well as checking the early terms
