Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers 4

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.

share|improve this answer
add comment

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.

share|improve this answer
    
What are generating functions, and how do they work? –  Brian J. Fink May 9 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 at 20:58
add comment
up vote 0 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
$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 at 0:30
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.