Summation of Fibonacci numbers $F_n$ with $n$ odd vs. even

Compare the summation below: $$\begin{align} \smash[b]{\sum_{i=1}^n F_{2i-1}}&=F_1+F_3+F_5+\cdots+F_{2n-1}\\ &=1+2+5+\cdots+F_{2n-1}\\ &=F_{2n}\\ \end{align} $$ with this one: $$\begin{align} \smash[b]{\sum_{i=1}^n F_{2i}}&=F_2+F_4+F_6+\cdots+F_{2n}\\ &=1+3+8+\cdots+F_{2n}\\ &=F_{2n+1}-1\\ \end{align}$$ When I first discovered these patterns I was amazed. Naively I had thought that an every-other-number sum of Fibonacci numbers would be the same pattern whether the parity of their indices was odd or even, but I was wrong! Why is the above true, where the summation of odd-indexed Fibonacci numbers is another Fibonacci number, but the even-indexed sum is a Fibonacci number minus 1?

Fibonacci numbers are defined by the recurrence relation,

$$F_n=F_{n-1}+F_{n-2},~~~F_1=F_2=1.$$

Rearranging, we have $F_{n-1}=F_n-F_{n-2}$. Letting $n=2k$,

$$F_{2k-1}=F_{2k}-F_{2(k-1)},$$

hence, the sum of odd-indexed Fibonacci numbers telescopes:

$$\sum_{k=2}^{m}F_{2k-1}=\sum_{k=2}^{m}(F_{2k}-F_{2(k-1)})=F_{2m}-F_{2}.$$

Since $F_1=F_2$,

$$\sum_{k=2}^{m}F_{2k-1}=F_{2m}-F_{2}\\ \implies F_1+\sum_{k=2}^{m}F_{2k-1}=F_{2m}\\ \implies \sum_{k=1}^{m}F_{2k-1}=F_{2m},$$

which is the formula the OP mentioned finding.

The derivation of the analogous formula for a sum of even-indexed Fibonacci numbers is highly similar. The key is the recurrence relation.

A clean way to see this is by using generating functions. Define $F(z) = \sum_{n \ge 0} F_n z^n$, take the recurrence: $$ F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1 $$ Multiply by $z^n$, sum over all valid values for $n$, i.e., $n \ge 0$, and recognize the resulting sums: $$ \frac{F(z) - F_0 - F_1 z}{z^2} = \frac{F(z) - F_0}{z} + F(z) $$ Solving: $$ F(z) = \frac{z}{1 - z - z^2} $$ We also have, if $A(z) = \sum_{n \ge 0} a_n z^n$ then: \begin{align} \sum_{n \ge 0} a_{2 n} z^{2 n} &= \frac{A(z) + A(-z)}{2} \\ \sum_{n \ge 0} a_{2 n + 1} z^{2 n + 1} &= \frac{A(z) - A(-z)}{2} \\ \sum_{n \ge 0} \left( \sum_{0 \le k \le n} a_k \right) z^n &= \frac{A(z)}{1 - z} \end{align} So, for even/odd Fibonacci numbers: \begin{align} F_e(z) &= \sum_{n \ge 0} F_{2 n} z^n \\ &= \frac{F(z^{1/2}) + F(- z^{1/2})}{2} \\ &= \frac{z}{1 - 3 z + z^2} \\ F_o(z) &= \sum_{n \ge 0} F_{2 n + 1} z^n \\ &= \frac{F(z^{1/2}) - F(- z^{1/2})}{2 z^{1/2}} \\ &= \frac{1 - z}{1 - 3 z + z^2} \\ \end{align} \begin{align} \sum_{n \ge 0} \left( \sum_{0 \le k \le n} F_{2 n} \right) z^n &= \frac{F(z^{1/2}) + F(- z^{1/2})}{2 (1 - z)} \\ &= \frac{z}{(1 - z) (1 - 3z + z^2)} \\ &= \frac{1 - z}{1 - 3 z + z^2} - \frac{1}{1 - z} \end{align} The first term is the generating function of the odd Fibonacci numbers, the second one is the generating function of the sequence of ones. Comparing coefficients: $$ \sum_{0 \le k \le n} F_{2 n} = F_{2 n + 1} - 1 $$ Similarly, as $F_0 = 0$: \begin{align} \sum_{n \ge 0} \left( \sum_{0 \le k \le n} F_{2 n + 1} \right) z^n &= \frac{F(z^{1/2}) - F(- z^{1/2})}{2 z^{1/2} (1 - z)} \\ &= \frac{1}{1 - 3z + z^2} \\ &= \frac{F_e(z) - F_0}{z} \end{align} The last expression corresponds to the even Fibonacci numbers shifted by one: $$ \sum_{0 \le k \le n} F_{2 n + 1} = F_{2 n + 2} $$ Note that we didn't need any premonition on what the sums would turn out to be.