Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For the following expression, find a simple formula which only involves one Fibonacci number. Then prove it by induction.

$$F_1+F_3+ \cdots +F_{2n+1} $$

I'm be appreciated for any help. I have no clue how to solve it at all...

share|cite|improve this question
For the first part (find the formula), list out the first few terms: $$1,~1+2,~1+2+5,~1+2+5+13,~\cdots$$ Evaluate the sums above. Notice a pattern? From this, you're supposed to hypothesize a formula for the $n$th term $F_1+F_3+\cdots+F_{2n+1}$. Whenever you are stuck not knowing what you're supposed to do next, the best thing to do is to review what you know you can do. (Here, you can list out terms and look for patterns!) The next step is to prove said speculative formula by induction. Do you know what induction is and how it works? – anon Mar 18 '13 at 7:11
Using $F_{2k+1}=F_{2k}+F_{2k-1}$ for each summand you can convert the problem to finding the sum of the first $2n$ Fibonacci numbers. – Martin Sleziak Mar 18 '13 at 14:33
up vote 8 down vote accepted

Well, we've got the recursive formula $F_n=F_{n-1}+F_{n-2}$ for Fibonacci numbers, with $F_1=F_2=1$ as usual. I'm assuming that's how you're starting at least.

Let's look at $n=1$. We claim the sum $F_1+\ldots+F_{2n+1}=F_{2n+2}$. We have $$ F_1+F_3=F_1+F_1+F_2=3=F_4=F_{2+2} $$ Looking forward, assume the $n$ case. Then $$ F_1+F_3+\ldots+F_{2n+1}+F_{2(n+1)+1}=F_{2n+2}+F_{2n+3}=F_{2n+4}=F_{2(n+1)+2}. $$ So we're done.

share|cite|improve this answer
Wow.... how do you do that? – user67253 Mar 18 '13 at 7:12

You can do this like in the game of checkers: whenever you've got to consecutive indices $i,i+1$ present in your sum, but none at $i+2$, you may take the lower index $i$, jump over and remove the (term $F_{i+1}$ with) index $i+1$, and land at $i+2$ (i.e., change the $F_i$ into $F_{i+2}$).

In the start you've got a range of odd indices from $1$ to $2n+1$ occupied. But since $F_1=F_2$, you may slide the index $1$ to position $2$. Now take this $2$, and jump over $3,5,7,\ldots,2n+1$ and land at $2n+2$. Since all other terms were removed, your sum is $F_{2n+2}$.

share|cite|improve this answer

I realize this is an old question, but a non-inductive proof is direct and quite simple, noting that $$F_{2k} + F_{2k+1} = F_{2k+2}.$$ Then the sum telescopes in an obvious way: $$\sum_{k=0}^n F_{2k+1} = \sum_{k=0}^n F_{2(k+1)} - F_{2k} = \sum_{k=1}^{n+1} F_{2k} - \sum_{k=0}^n F_{2k} = F_{2(n+1)} - F_0 = F_{2(n+1)}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.