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

• If you know (or you are able to prove) that $F_{2n}=F_n L_n$, where $L_n$ is a Lucas number, the problem boils down to showing that $L_n=F_{n-1}+F_{n+1}$, trivial by induction. Oct 30, 2015 at 16:43
• @Jean-ClaudeArbaut sorry it was an accident I was editing on my phone Oct 30, 2015 at 16:59
• @JackD'Aurizio we haven't started using the Lucas number Oct 30, 2015 at 16:59

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.

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

• We're not using matrices to solve but thank you Oct 30, 2015 at 16:58
• @lhf This is one of those things which is so painfully obvious in retrospect Oct 30, 2015 at 16:58

(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