Fibonacci Identity Inductive Proof

Question

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.

Answer 1

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

Answer 2

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