Combinatorics -- Fibonacci: formula for $F_1+F_3+ \cdots +F_{2n+1} $ 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...
 A: 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.
A: 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}$.
A: 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)}.$$
