Fibonacci Numbers – Summation of Fibonacci Numbers with Odd and Even n

fibonacci-numbers

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?

Best Answer

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.

Related Solutions

Discrete Mathematics – Fibonacci Addition Law $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

With Fibonacci numbers usually there are multiple ways of proving identities.

One way (which is one of my favourites) to prove your identity is the following:

Consider the following problem:

A person climbs up $\displaystyle n$ steps, by taking either one step, or two steps at a time.

The total number of ways the person can climb up all the $\displaystyle n$ steps is $\displaystyle F_{n+1}$ (Why?)

Now consider climbing $\displaystyle m+n-1$ steps and split into the cases when the person lands on step $\displaystyle n$ and the cases when the person lands on step $\displaystyle n-1$ and takes two steps at that point (and so does not land on step $\displaystyle n$ in those cases). These two cases cover all possibilities, and so we have:

$$\displaystyle F_{m+n} = F_{n+1}F_{m} + F_{n}F_{m-1}$$

[Math] Sum of product of Fibonacci numbers

Let's use $$ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - (-1)^n \phi^{-n} \right) $$ where $\phi$ is a Golden ratio constant $\phi = \frac{\sqrt{5}+1}{2}$. Now the sum reduces to the combination of geometric sums: $$ \begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^k - (-1)^k \phi^{-k}\right)\left(\phi^{n-k} - (-1)^{n-k} \phi^{k-n}\right) \\ &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^n - (-1)^k \phi^{n-2k} - (-1)^{n-k} \phi^{2k-n} + (-1)^n \phi^{-n} \right) \\ &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) - \frac{\phi^{n}}{5} \sum_{k=1}^{n-1} \left( -\phi^{-2}\right)^{k} - \frac{(-1)^{n}}{5} \phi^{-n} \sum_{k=1}^{n-1} \left(-\phi^2\right)^k \end{eqnarray} $$ Using the geometric sum $\sum_{k=1}^{n-1} x^k = \frac{x-x^n}{1-x}$ we get: $$\begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) + \frac{2}{5} \frac{\phi^{n-1} + (-1)^n \phi^{1-n}}{\phi + \phi^{-1}} \\ &=& \frac{n-1}{5} L_n + \frac{2}{5} F_{n-1} \end{eqnarray} $$ where $L_n$ denotes $n$-th Lucas number.

Quick sanity check in Mathematica:

In[84]:= Table[
 Sum[Fibonacci[k] Fibonacci[n - k], {k, 1, n - 1}] == (n - 1)/
    5 LucasL[n] + 2/5 Fibonacci[n - 1], {n, 1, 6}]

Out[84]= {True, True, True, True, True, True}

The sum stated in the edited question is obtained by replacing $n$ with $n+1$ in the sum evaluated above: $$ \sum_{k=1}^{n} F_k F_{n+1-k} = \frac{n}{5} L_{n+1} + \frac{2}{5} F_n $$

Best Answer

Related Solutions

Discrete Mathematics – Fibonacci Addition Law $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

[Math] Sum of product of Fibonacci numbers

Related Question