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

• What are the base values of F ? – Shailesh Sep 14 '15 at 3:56
• Oh these are for fibonacci numbers. – 277roshan Sep 14 '15 at 3:56
• You can use second principle of finite induction. Use two previous relations to prove the third – Shailesh Sep 14 '15 at 4:03
• It seems like the terms get as big as F(2k+4) if I am taking k, k+1 and solving for k+2. While trying to solve the process seems quite convoluted. I still cannot get to the solution. – 277roshan Sep 14 '15 at 4:17
• – Martin Sleziak Nov 7 '15 at 20:05

We have $F_{n}F_{n+1} - F_{n-2}F_{n-1} = F_{2n-1}$ (See link).
Assume that $F_{2k} = F_k(F_{k-1}+F_{k+1})$.
We prove that $$F_{2(k+1)} = F_{k+1}(F_{k} + F_{k+2}).$$
One has $$F_{2(k+1)} = F_{2k+1} + F_{2k} = F_k(F_{k-1}+F_{k+1}) + F_{k+1}F_{k+2} - F_{k-1}F_{k} = F_{k+1}(F_k+F_{k+2}).$$