# Fibonacci Identity Inductive Proof

I have been trying to prove the following Fibonacci Identity using induction:

$F_{2n+2} = 2F_nF_{n+1}+F_{n+1}^2$

To assist with this proof I have been told that:

$F_{2n+1}=F_n^2+F_{n+1}^2$

I can do the Base Case and Inductive Hypothesis myself, but need help with the actual proof.

If possible the proof would not involve a Fibonacci Matrix or Binet's Formula.

• Seems like a pity to miss out on the Q-matrix approach, but the tools provided are indeed enough. – Joffan Mar 6 '17 at 17:27

You already proved the case $n=0$. Assume that the claim is true up to $n-1$, that is:
$F_{2n}=2F_{n-1}F_n+F^2_n$
Now let us prove the claim for $n$:
\begin{align*} F_{2n+2}&=F_{2n+1}+F_{2n}=\\ &=F^2_n+F^2_{n+1}+2F_{n-1}F_n+F^2_n=\quad \text{(here we used induction hyp + your identity)}\\ &=2F_n(F_n+F_{n-1})+F^2_{n+1}=\\ &=2F_nF_{n+1}+F^2_{n+1} \end{align*}
If you prove for first that $F_{2n}=F_n L_n$, your claim boils down to showing that $$L_{n+1} = 2F_n+F_{n+1}$$ holds, and that is very simple (always by induction).
• @ScottB.: the $n$-th Lucas number. Lucas numbers are defined through $L_0=2,\,L_1=1$ and $L_{n+2}=L_{n+1}+L_n$ (same recurrence relation of Fibonacci numbers, different starting values). – Jack D'Aurizio Mar 6 '17 at 17:34