1
$\begingroup$

I need to prove the following with induction:

n∑i=1 F(2i-1) = F(2n) for all n >= 1

I am stuck in my inductive step:

  • n∑i=1 F(2i-1) = n∑i=1 F(2i-1) + F(2(n + 1) -1)

  • = F(2n) + F(2(n + 1)-1)

  • = F(2n) + F(2n + 1)

I am trying to get to F(2n + 2).

I know the following recursive definition of Fibonacci numbers: F(n) = F(n-1) + F(n-2), How can I use it to reach my answer?

Thanks a lot!

$\endgroup$
  • $\begingroup$ Um, you already have. F(2n + 2) by definition = F(2n + 1) + F(2N). $\endgroup$ – fleablood Oct 21 '15 at 22:00
1
$\begingroup$

The statement seems to be $$ \sum_{i=1}^n F(2i-1)=F(2n),\qquad n\ge1 $$ The base case, $n=1$, is obvious because $F(1)=1$ and $F(2)=1$.

Assume it's the case for $n$; then $$ \sum_{i=1}^{n+1} F(2i-1)= \biggl(\,\sum_{i=1}^{n} F(2i-1)\biggr)+F(2(n+1)-1)= F(2n)+F(2n+1) $$ and the definition of the Fibonacci sequence gives the final step: $$ F(2n)+F(2n+1)=F(2n+2)=F(2(n+1)) $$

$\endgroup$
  • $\begingroup$ Oh ok, so whats helped me most is that you can justify the final step by the definition of a Fibonacci sequence. Thanks! $\endgroup$ – coders Oct 21 '15 at 22:19
1
$\begingroup$

Sum up the recurrence relations: $$\sum_{i=1}^n F_{2i}=\sum_{i=1}^n F_{2i-1}+\sum_{i=1}^n F_{2i-2}=\sum_{i=1}^n F_{2i-1}+\sum_{i=0}^{n-1} F_{2i}$$ As $F_0=0$, this equality simplifies to: $$F_{2n}=\sum_{i=1}^n F_{2i-1}.$$

$\endgroup$

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.