# Combinatorics — Fibonacci

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...

-
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
–  Martin Sleziak Mar 18 '13 at 14:29
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

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.
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}$.