Nikhil Ravi

Even Fibonacci Numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$ , the first $10$ terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_{n-1} + F_{n-2}, \quad F_1 = 1, \quad F_2 = 2.

By observation, we can see that every third term is even. We can use this fact to generate the sequence and sum the even terms.

S_n = \sum_{i=1}^n F_{3i},

where $n$ is the number of terms to sum.

The term $F_{3n}$ is the largest term and it can not exceed the limit of $4,000,000$ . We can use this fact to determine the number of terms to sum.

The Binet formula gives a closed form for the Fibonacci sequence:

F_n = \frac{\phi^n - \psi^n}{\sqrt{5}},

where $\phi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$ .

Notice that $\psi^n \to 0$ as $n \to \infty$ . Therefore, we can approximate the number of terms to sum as:

\begin{equation} 3n < \frac{\ln(4,000,000 \sqrt{5})}{\ln(\phi)} \end{equation}

By recursion, we note that:

\begin{align*} F_{i+3} &= F_{i+2} + F_{i+1} = F_{i+2} + F_{i+2} - F_{i}\\ &= 2F_{i+2} - F_{i} = 2 (F_{i+1} + F_{i}) - F_{i}\\ &= 2F_{i+1} + F_{i} = 2(F_{i} + F_{i-1}) + F_{i}\\ &= 3F_{i} + 2F_{i-1} = 3F_{i} + 2(F_{i} - F_{i-2})\\ &= 4F_{i} + F_{i} - 2F_{i-2} = 4F_{i} + F_{i-1} + F_{i-2} - 2F_{i-2}\\ &= 4F_{i} + F_{i-1} - F_{i-2}\\ &= 4F_{i} + F_{i-3}\\ \Rightarrow\quad 4F_{i} + F_{i-3} - F_{i+3} &= 0\\ \end{align*}

This gives us a recurrence relation for the even terms and using the definition of $S_n$ , we sum over the recurrence relation by setting $i = 3k$ :

\begin{align*} 4\sum_{k=1}^n F_{3k} + \sum_{k=1}^n F_{3k-3} - \sum_{k=1}^n F_{3k+3} &= 0, \end{align*}

where the first term is simply $4S_n$ . In the second and third terms, we can substitute $j=k-1$ and $j=k+1$ , respectively, to get:

\begin{align*} 4S_n + \sum_{j=0}^{n-1} F_{3j} - \sum_{j=2}^{n+1} F_{3j} &= 0\\ 4S_n + (F_0 + \sum_{j=1}^{n} F_{3j} - F_{3n}) - (\sum_{j=1}^{n} F_{3j} + F_{3n+3} - F_{3}) &= 0\\ 4S_n + (F_0 + S_{n} - F_{3n}) - (S_{n} + F_{3n+3} - F_{3}) &= 0\\ 4S_n - (F_{3n+3}+F_{3n}) + (F_0 + F_{3}) &= 0\\ 4S_n - (F_{3n+2} + F_{3n+1} + F_{3n}) + (F_2 - F_1 + F_2 + F_1) &= 0\\ 4S_n - 2F_{3n+2} + 2F_2 &= 0. \end{align*}

Thus, we have a closed form for the sum of the even terms:

\begin{equation} S_n = \frac{F_{3n+2}-F_2}{2}. \end{equation}

import numpy as np

First, we need to find the largest term that does not exceed $4,000,000$ . We can use the relation we derived in (1) to find the largest term's Fibonacci index:

index_of_largest = np.floor(
    np.log(4e6 * np.sqrt(5)) / np.log((1 + np.sqrt(5)) / 2)
).astype(int)
print(f"The largest term in our series in F_{{{index_of_largest}}}")

The largest term in our series in F_{33}

F_n = lambda n: ((1 + np.sqrt(5)) ** n - (1 - np.sqrt(5)) ** n) / (2**n * np.sqrt(5))
sum_of_evens = ((F_n(index_of_largest + 2) - F_n(2)) / 2).astype(int)
 
print(f"The sum of the even-valued terms is {sum_of_evens}")

The sum of the even-valued terms is 4613732