I recently uncovered some old math that I did for fun in my first semester of college while I was taking a course on discrete mathematics. On a problem set, we had to determine the sum of the first $n$ even Fibonacci numbers and also the sum of the first $2n$ odd Fibonacci numbers. However, we were not asked to find the sum of the first $n$ odd Fibonacci numbers, which I decided to investigate.

For those unfamiliar, the Fibonacci sequence is defined as follows: $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. The first few terms of the sequence are $0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots$. The Fibonacci numbers with odd values are $1, 1, 3, 5, 13, 21, \ldots$. Observe that the indices of these Fibonacci numbers are not divisible by 3, i.e., $F_1, F_2, F_4, F_5, F_7, F_8, \ldots$. These indices are given by $\lfloor \frac{3i-1}{2} \rfloor$ for $i \geq 1$, which is also A001651 in the OEIS.

Now I wanted to find the sum of the first $n$ odd-valued Fibonacci numbers. The sequence of partial sums for the first few $n$ corresponds to A174542 in the OEIS. As of making this post, the only formulas in the OEIS were either recursive or only found the sum for the first $2n$ or $2n+1$ odd-valued Fibonacci numbers. There was no closed-form formula for the sum of the first $n$ odd-valued Fibonacci numbers. So I set out to find one, and I was able to derive the following result:

Theorem: The sum of the first $n$ Fibonacci numbers with odd values is given by:

\begin{equation*} \sum_{i=1}^{n} F_{\left\lfloor \frac{3i-1}{2} \right\rfloor} = \frac{1}{2} \left( F_{3 \left\lfloor \frac{n+1}{2} \right\rfloor} + F_{3 \left\lfloor \frac{n}{2} \right\rfloor + 1} - 1 \right) \end{equation*}

Proof: We apply induction on $n$. Let

\begin{eqnarray*} P(n) = \sum_{i=1}^{n} F_{\left\lfloor \frac{{3i-1}}{2} \right\rfloor} = \frac{1}{2} \left( F_{3 \cdot \left\lfloor {\frac{{n+1}}{2}} \right\rfloor} + F_{3 \cdot \left\lfloor \frac{n}{2} \right\rfloor + 1} - 1 \right) \end{eqnarray*}

Base case:

\begin{eqnarray*} P(1) = \sum_{i=1}^{1} F_{\left\lfloor \frac{{3i-1}}{2} \right\rfloor} &=& \frac{1}{2} \left( F_{3 \cdot \left\lfloor {\frac{{1+1}}{2}} \right\rfloor} + F_{3 \cdot \left\lfloor \frac{1}{2} \right\rfloor + 1} - 1 \right)\\ F_{\left\lfloor \frac{{3(1)-1}}{2} \right\rfloor} &=& \frac{1}{2} \left( F_{3 \cdot {1}} + F_{3 \cdot 0 + 1} - 1 \right)\\ F_{\left\lfloor \frac{{2}}{2} \right\rfloor} &=& \frac{1}{2} \left( F_{3} + F_{1} - 1 \right)\\ F_{1} &=& \frac{1}{2} \left( 2 + 1 - 1 \right)\\ 1 &=& 1 \end{eqnarray*}

Thus, $P(1)$ is true.

Inductive step: Assume that the statement holds for some integer $n \geq 1$. We examine the sum for $n+1$:

\begin{align*} \sum_{i=1}^{n+1} F_{\left\lfloor \frac{3i-1}{2} \right\rfloor} &= \left( \sum_{i=1}^{n} F_{\left\lfloor \frac{3i-1}{2} \right\rfloor} \right) + F_{\left\lfloor \frac{3(n+1)-1}{2} \right\rfloor} \end{align*}

By applying the inductive hypothesis to the summation on the right, we obtain:

\begin{align*} \sum_{i=1}^{n+1} F_{\left\lfloor \frac{3i-1}{2} \right\rfloor} &= \frac{1}{2} \left( F_{3 \left\lfloor \frac{n+1}{2} \right\rfloor} + F_{3 \left\lfloor \frac{n}{2} \right\rfloor + 1} - 1 \right) + F_{\left\lfloor \frac{3n+2}{2} \right\rfloor} \end{align*}

To complete the proof, we must demonstrate that this expression simplifies to the formula for $n+1$. Due to the behavior of the floor function, we consider the cases where $n$ is even and odd separately.

Case 1: $n$ is even. Let $n = 2k$ for some integer $k \geq 1$. The term added is $F_{\left\lfloor \frac{6k+2}{2} \right\rfloor} = F_{3k+1}$. Using the inductive hypothesis for $P(2k)$:

\begin{align*} P(2k+1) &= \frac{1}{2} \left( F_{3 \cdot \left\lfloor \frac{2k+1}{2} \right\rfloor} + F_{3 \cdot \left\lfloor \frac{2k}{2} \right\rfloor + 1} - 1 \right) + F_{3k+1} \\ &= \frac{1}{2} \left( F_{3k} + F_{3k+1} - 1 \right) + F_{3k+1} \\ &= \frac{1}{2} \left( F_{3k} + F_{3k+1} - 1 + 2F_{3k+1} \right) \\ &= \frac{1}{2} \left( F_{3k} + 3F_{3k+1} - 1 \right) \end{align*}

We know that $3F_{3k+1} = 2F_{3k+1} + F_{3k+1}$. Also, $F_{3k} + 2F_{3k+1} = F_{3k} + F_{3k+1} + F_{3k+1} = F_{3k+2} + F_{3k+1} = F_{3k+3}$. Thus,

\begin{align*} P(2k+1) &= \frac{1}{2} \left( F_{3k+3} + F_{3k+1} - 1 \right). \end{align*}

Checking the formula for $n+1 = 2k+1$:

\begin{align*} \frac{1}{2} \left( F_{3 \cdot \left\lfloor \frac{2k+2}{2} \right\rfloor} + F_{3 \cdot \left\lfloor \frac{2k+1}{2} \right\rfloor + 1} - 1 \right) &= \frac{1}{2} \left( F_{3(k+1)} + F_{3k+1} - 1 \right) \\ &= \frac{1}{2} \left( F_{3k+3} + F_{3k+1} - 1 \right) \end{align*}

The case holds.

Case 2: $n$ is odd. Let $n = 2k-1$ for some integer $k \geq 1$. The term added is $F_{\left\lfloor \frac{3(2k)-1}{2} \right\rfloor} = F_{\left\lfloor \frac{6k-1}{2} \right\rfloor} = F_{3k-1}$. Using the inductive hypothesis for $P(2k-1)$:

\begin{align*} P(2k) &= \frac{1}{2} \left( F_{3 \cdot \left\lfloor \frac{2k}{2} \right\rfloor} + F_{3 \cdot \left\lfloor \frac{2k-1}{2} \right\rfloor + 1} - 1 \right) + F_{3k-1} \\ &= \frac{1}{2} \left( F_{3k} + F_{3k-2} - 1 \right) + F_{3k-1} \\ &= \frac{1}{2} \left( F_{3k} + F_{3k-2} - 1 + 2F_{3k-1} \right) \\ &= \frac{1}{2} \left( F_{3k} + (F_{3k-2} + F_{3k-1}) + F_{3k-1} - 1 \right) \\ &= \frac{1}{2} \left( F_{3k} + F_{3k} + F_{3k-1} - 1 \right) \\ &= \frac{1}{2} \left( 2F_{3k} + F_{3k-1} - 1 \right) \\ &= \frac{1}{2} \left( F_{3k} + (F_{3k} + F_{3k-1}) - 1 \right) \\ &= \frac{1}{2} \left( F_{3k} + F_{3k+1} - 1 \right) \end{align*}

Checking the formula for $n+1 = 2k$:

\begin{align*} \frac{1}{2} \left( F_{3 \cdot \left\lfloor \frac{2k+1}{2} \right\rfloor} + F_{3 \cdot \left\lfloor \frac{2k}{2} \right\rfloor + 1} - 1 \right) &= \frac{1}{2} \left( F_{3k} + F_{3k+1} - 1 \right) \end{align*}

The case holds.

Since both cases hold, $P(n+1)$ is true. By the principle of mathematical induction, the theorem is true for all $n \geq 1$.