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 ? Commented Sep 14, 2015 at 3:56
• Oh these are for fibonacci numbers. Commented Sep 14, 2015 at 3:56
• You can use second principle of finite induction. Use two previous relations to prove the third Commented Sep 14, 2015 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. Commented Sep 14, 2015 at 4:17
• Commented Nov 7, 2015 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}).$$

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.