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

-
What are generating functions, and how do they work? –  Brian J. Fink May 9 '14 at 20:44
@BrianJ.Fink, (formal) power series, where the coefficients are the numbers we are interested in. See e.g. Wilf's "generatingfunctionology" for the whole enchilada (it goes quite far, but is quite approachable at least starting up). –  vonbrand May 9 '14 at 20:58

By adding the two summations together, you get: \begin{align} \sum_{i=1}^n F_{2i-1}+\sum_{i=1}^n F_{2i}&=F_{2n}+F_{2n+1}-1\\ &=F_{2n+2}-1\\ &=\sum_{i=1}^{2n}F_i\\ \end{align} In this way, both patterns can be mathematically justified—although the mechanics behind this phenomenon are still somewhat of a mystery to me.

Update: The two formulas can be merged into one in the following way: \begin{align} 0&=F_0\\ 1&=F_1\\ \smash[b]{\sum_{i=1}^n F_{2i-1}}&=F_{2n}\\ &=F_{2n+0}-0\\ &=F_{2n+0}-F_0\\ \smash[b]{\sum_{i=1}^n F_{2i}}&=F_{2n+1}-1\\ &=F_{2n+1}-F_1\\ \therefore\smash[b]{\sum_{i=1}^n F_{2i+r-1}}&=F_{2n+r}-F_r &r=\begin{cases} 0, &\text{if 2i+r-1 is odd}\\ 1, &\text{if 2i+r-1 is even} \end{cases} \end{align}

-

Here's a slightly sneaky way to remove the disparity between the two sums: Use the indexing convention $F_0=F_1=1$. You'll then find that

$$\sum_{i=1}^n F_{2i-1}=F_{2n}-1$$ and $$\sum_{i=1}^n F_{2i}=F_{2n+1}-1$$

Voila! The pattern is the same for both!

Added later: Here's another way to make the two patterns look alike, without playing around with the indexing convention (indeed, it doesn't matter what convention you use):

$$F_1+F_3+\cdots+F_{2n-1}=F_{2n}-F_0$$ and $$F_2+F_4+\cdots+F_{2n}=F_{2n+1}-F_1$$

In general, if $m$ and $n$ have the same parity and $m\lt n$, then

$$F_m+F_{m+2}+\cdots+F_n=F_{n+1}-F_{m-1}$$

-
$F_1=F_2=1$—that's standard indexing. $F_0=0$. Any other convention would not comport with Binet's Formula. –  Brian J. Fink May 10 '14 at 0:30