Prove the following by using mathematical induction. The Fibonacci sequence is defined as a recursive equation: $F_{1}=1$;$F_{2}=1$; and $F_{k}$=$F_{k-1}$+$F_{k-2}$. For all n∈N, the Fibonacci relation holds $$\sum_{i=0}^{n-1} F_{2i+1} = F_{2n}$$ I have seen many variations of the fibonacci sequence but have not seen it in this form and am confused on how to solve it with induction. Any help would be greatly appreciated. I know you have to start with one, then k, then k+1.

  • $\begingroup$ It isn't entirely clear what you are asking. If you know the solution is the Fibonacci sequence, perhaps you are asking about how to demonstrate that. In any case if you are trying to prove something by "induction", start by identifying the basis step and then the induction step. $\endgroup$ – hardmath Nov 11 '18 at 5:22

OK, so just follow the basic proof schema for induction:

Base: show that the claim is true for $n=1$. This means that you need to show that $\sum_{i=0}^{1-1}F_{2i+1}=F_{2}$

Well, the LHS is just $F_1$, which is 1, and that indeed equals $F_2$

Step: Take some arbitrary number $k$. Assume it is true that $\sum_{i=0}^{k-1}F_{2i+1}=F_{2k}$

We now have to show that $\sum_{i=0}^{(k+1)-1}F_{2i+1}=F_{2(k+1)}$

Can you do that?

  • $\begingroup$ $$Let\ P(n)\ be: F_1+F_3+F_5+⋯+F_{(2(n-1)+1)}=F_{2n}.$$ $$We\ must\ first\ show\ that\ P(n), for\ n=1\ is\ true.$$ $$For\ n=1; F_1=F_2$$ $$Therefore\ P(n)\ is\ true\ for\ n=1.$$ $$Assume\ P(n)\ to\ be\ true\ for\ n=k, where\ k∈N.$$ $$F_1+F_3+F_5+⋯+F_{(2(k-1)+1)}=F_{2k}$$ $$Then\ P(k+1) is: F_1+F_3+F_5+⋯+F_{(2k+1)}=F_{(2(k+1))}$$ We then prove that P(k+1) is true $$F_{(2k-1)}=F_{(2(k))}$$ $$F_{(2k-1)}+F_{(2k+1)}=F_{(2(k))}+F_{(2k+1)}$$ Then what would be the next step? @Bram28 $\endgroup$ – Karl Tesch Nov 11 '18 at 17:41
  • $\begingroup$ @KarlTesch Yes, perfect set-up! OK, but when you prove $P(k+1)$, you can do: $$F_1+F_3+...+F_{2k+1}=$$$$F_1+F_3+...+F_{2(k-1)+1}+F_{2k+1}\overset{Inductive Hypothesis}{=}$$$$F_{2k}+F_{2k+1}=F_{2k+2}=F_{2(k+1)}$$ $\endgroup$ – Bram28 Nov 11 '18 at 19:32

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.