0

I am trying to prove by induction the following proposition of the fibonacci sequence:

The fibonacci sequence is defined recursively as: $f_1 = 1$, $f_2 = 1$, and that for all integers $k>=1$, $f_{k+1} = f_{k+1} +f_k $

Propostion I am trying to prove:

$\sum_{i=1}^{k} F_{2i}=F_{2k+1}-1$ for all $k∈N$

So far I have this:

Base case:

For $F_1$: $\sum_{i=1}^{k} F_{2i}$ = $F_{2(1)}$ = $F_{2}$ This is true.

Induction Hypothesis:

$\sum_{i=1}^{n+1} F_{2i}$ = $F_{2(n+1)}$

I am not sure if what I have so far is correct.

I have brainstormed this also:

That $f_2 = f_3 - 1$. And that $f_2\:+\:f_4\:+\ldots+f_{2n}=f_{2n+1}-1$. By adding $f_{2n+2}$ to both sides, you get $f_2\:+\:f_4\:+...+f_{2n} + f_{2n+2}= f_{2n+2}+f_{2n+1}-1$. And $f_{2n+2}+f_{2n+1} = f_{2n+3}$.

I am not sure how to prove the proposition by induction properly. I have a general understanding of how induction works and why the proposition is true, but I am having trouble proving it with induction steps. I think I need to somehow get to $f_{2n} = f_{2(n+1)+1}-1$, but I am struggling with that. I haven't practiced much strong induction yet, so I am only looking for a simple proof. To provide context as to why I am doing this exercise: I am planning to use this proof as a base for me to refer back to when doing more complex proofs that also involve the fibonacci sequence.

Thank you for all the help or any proofs provided.

sam
  • 123
  • Probable duplicate of https://math.stackexchange.com/questions/4017822/let-a-1-a-2-1-a-3-2-and-a-n-a-n-1a-n-2-for-n-ge3-prove-that-a-1 – lhf Feb 24 '21 at 19:19
  • @DietrichBurde not really, I am not completely understanding the steps done and how to apply them to my question. I know they are very similar, but I still need help. – sam Feb 24 '21 at 19:22
  • On the LHS, there is an $n$, but there isn't an $n$ on the RHS. Is it possible if you clarify? – Joe Feb 24 '21 at 19:22
  • It looks to me like you have everything you need to prove it, but it's not organized properly. In the inductive step, your inductive hypothesis is that $\sum_{i=1}^n f_{2i}=f_{2n+1}-1$. This is the part that you assume. What you want to prove is that $\sum_{i=1}^{n+1} f_{2i}=f_{2(n+1)+1}-1$, which you've proven using the inductive hypothesis. – Kevin Long Feb 24 '21 at 19:26
  • Can someone explain to me how to set up the base case and induction hypothesis for the proof and how they solved it? I tried it out but I think it may be incorrect. – sam Feb 24 '21 at 19:26
  • @KevinLong I am not really sure how to organize it properly and I don't really know how to prove $\sum_{i=1}^{n+1} f_{2i}=f_{2(n+1}+1}$. I know that it is what I aiming to prove, but I don't know how to properly show it – sam Feb 24 '21 at 19:28
  • @charles I'm a little confused here, because it looks to me that you have proven it. You took $\sum_{i=1}^n f_{2i}=f_{2n+1}-1$, which is your inductive hypothesis, added $f_{2n+2}$ to both sides, and got $\sum_{i=1}^{n+1} f_{2i}=f_{2n+1}+f_{2n+2}-1=f_{2n+3}-1$, which is $f_{2(n+1)+1}-1$. It seems like you're done. I only meant that what you called your "induction hypothesis" was in fact what you were trying to prove, and not your hypothesis. – Kevin Long Feb 24 '21 at 19:32
  • @KevinLong I'm confused, can you please explain to me why I'm done and if what I've done is correct? What should my induction hypothesis be? I honestly thought I did the whole thing wrong so I can you explain to me why it is right? I am having trouble understanding why it works. Thanks for your help so far! – sam Feb 24 '21 at 19:39
  • @charles J.G.'s answer says everything you need. – Kevin Long Feb 24 '21 at 19:47

1 Answers1

1

We want to prove $\varphi(n)$ for all $n\ge1$, with $\varphi(n)$ meaning $\sum_{i=1}^nF_{2i}=F_{2n+1}-1$. The principle of mathematical induction states that if $\varphi(1)$ (base case) and $\forall k\ge1(\varphi(k)\to\varphi(k+1))$ (induction step), $\forall n\ge1(\varphi(n))$. Your calculations have proved the base case $F_2=F_3-1$ and the induction step viz.$$\sum_{i=1}^kF_{2i}=F_{2k+1}-1\implies\sum_{i=1}^{k+1}F_{2i}=\sum_{i=1}^kF_{2i}+F_{2k+2}=F_{2k+1}-1+F_{2k+2}=F_{2k+3}-1,$$so you're done.

(The principle is usually stated as starting at $0$; $\varphi(0)$ equates an empty sum, i.e. $0$, to $F_1-1$, so we could have taken an $n=0$ base step. But based on your calculations I started at $n=1$, which is a common definition of $\Bbb N$.)

J.G.
  • 115,835
  • Thank you for your answer! Can you explain to me why the base case is true? I don't completely understand why $F_2 = F_3 - 1$ is proven by my calculations. I also don't understand why base case of $F_{2i} = F_2$ is true. I also don't completely understand what is my induction hypothesis. I know I am asking a lot, but if you have time, I would really appreciate the help! – sam Feb 26 '21 at 19:25
  • @Charles For $n\ge0$, $\sum_{i=1}^na_i$ is a sum of $n$ terms. To satisfy $\sum_{i=1}^ka_i+a_{k+1}=\sum_{i=1}^{k+1}a_i$, a sum of $1$ term $a_1$ is just $a_1$, while the sum of $0$ terms is $0$. We can start at $n=0$ with base case $0=F_1-1$, or at $n=1$ with base case $F_2=F_3-1$. An inductive proof that $\varphi(n)$ for all $n\ge N$ has base case $\varphi(N)$, inductive step $\varphi(k)\to\varphi(k+1)$ (with $k$ running from $N$ onwards), and inductive hypothesis $\varphi(k)$; in this case, $\varphi$ has the meaning I gave. – J.G. Feb 26 '21 at 19:31
  • Okay thanks so much! – sam Feb 26 '21 at 19:33