0
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for answering, but I don't understand what Ln is in that equation. $\endgroup$ – Scott B. Mar 6 '17 at 17:17
  • $\begingroup$ @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). $\endgroup$ – Jack D'Aurizio Mar 6 '17 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.