<s>[INST] Prove by induction for $F(2n) = F(n)[F(n-1) + F(n+1)]$ for all $n\ge 1$ I am totally stumped by this question. I have proved the base case. Then for $k$ is $1$ assume the relation to be true. When I try to prove for $k+1$, the terms just do not simplify to what I want. Is there something missing in the question or is it that I am just not being able to solve the question?
 [/INST] Assume that $F_{2n} = F_n[F_{n-1}+F_{n+1}]$ and use this (the n case) to show that the n+1 case, i.e. $F_{2(n+1)} = F_{2n+2} = F_{n+1}[F_n+F_{n+2}]$, is true
We have $F^2_{n+1}-F_nF_{n+2} = (-1)^n$
$F_{n+1}[F_n+F_{n+2}]$
= $F_{n+1}F_n+F_{n+1}F_{n+2}$
= $F_{n+1}F_n+F^2_{n+1} + F_{n+1}F_n$ since $F_{n+2} = F_{n+1}+ F_n$ for fibonacci numbers
= $(-1)^n + F_nF_{n+2} + 2F_nF_{n+1}$
= $(-1)^n + F_nF_{n+1} + F^2_n + 2F_nF_{n+1}$
= $(-1)^n + F_nF_{n+1} + F_{n-1}F_{n+1} + (-1)^{n-1} + 2F_nF_{n+1}$
= $F_nF_{n+1} + F^2_{n-1} + F_{n-1}F_n + 2F_nF_{n+1}$
= $F_nF_{n+1} + F_{n-2}F_n + (-1)^{n-2}+ F_{n-1}F_n + 2F_nF_{n+1}$
= $3F_nF_{n+1} + F_{n-2}F_n + (-1)^{n-2}+ F_{n-1}F_n$
= $3F_nF_{n+1} + F_{n-2}F_{n+1} - F_{n-2}F_{n-1} + (-1)^{n-2}+ F_{n-1}F_n$ since $F_n = F_{n+1}-F_{n-1}$
= $3F_nF_{n+1} + F_nF_{n+1} - F_{n-1}F_{n+1} - F_{n-2}F_{n-1} + (-1)^{n-2}+ F_{n-1}F_n$
= $3F_nF_{n+1} + F^2_n + F_nF_{n-1}- F_{n-2}F_{n-1} + (-1)^{n-2}+ F_{n-1}F_n$ since $F_n = F_{n+1}-F_{n-1}$
= $3F_nF_{n+1} + 2F_nF_{n-1} - F_{n-1}F_{n-2} + F_{n-1}F_{n+1} -F_{n-1}F_{n+1} + (-1)^{n-1} + (-1)^{n-2}$
= $3F_nF_{n+1} + 2F_nF_{n-1} - F_{n-1}F_{n-2}$
= $3F_nF_{n+1}+ 3F_nF_{n-1} - F_nF_{n-1}- F_{n-1}F_{n-2}$
= $3F_n(F_{n+1}+F_{n-1})- F_nF_{n-1}- F_{n-1}F_{n-2}$
= $3F_{2n} - F_{n-1}[F_n+ F_{n-2}]$ using our induction hypothesis
= $3F_{2n} - F_{2(n-1)}$
= $2F_{2n} + F_{2n-1}$ since $F_{2n}-F_{2(n-1)} = F_{2n-1} (F_{2(n-1)}=F_{2n-2)}$
= $F_{2n} + F_{2n+1}$ since $F_{2n+1} = F_{2n} + F_{2n-1}$
= $F_{2n+2} = F_2{n+1}$
Since we have shown that $F_n+1[F_(n)+F_(n+2)] = F_2(n+1)$ (the n+1 case) is true from assuming the n case $F_2n = F_n[F_(n-1)+F_(n+1)]$ to be true and we know that the base case n=1 is true, we have proven $F_2n = F_n[F_(n-1)+F_(n+1)]$ inductively.
$F^2_n+1-F_nF_n+2 = (-1)^n$ can be proven pretty quickly by induction. I could not solve this problem either without the above identity.
</s>