Project Euler Problem 2

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.

The naive approach

We want to sum all the even Fibonacci numbers up to some limit.

We'll use a slightly different convention from Project Euler. The recurrence relation for the $n^\text{th}$ Fibonacci number is $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$, the convention OEIS A000045 uses, so the first 13 terms are

We could generate all the Fibonacci numbers up to that limit and just sum the even ones:

function sum_even_fibonacci_naive(limit)
    result = 0

    a, b = 0, 1
    while a ≤ limit
        iseven(a) && (result += a)
        a, b = b, a + b
    end

    return result
end

Benchmarking sum_even_fibonacci_naive(4 * 10^6) we get 17.662 ns, which is already fast enough for the problem. But there's a cooler method!

A recurrence for the even Fibonacci numbers

Notice that $F_3 = 2$, $F_6 = 8$, $F_9 = 34$, and $F_{12} = 144$. So every third number is even, and all the others are odd. This is because $F_0 = 0$ is even and $F_1 = 1$ is odd, so $F_2 = F_1 + F_0$ will be odd because $\text{even} + \text{odd} = \text{odd}$ by parity. Then $F_3 = F_2 + F_1$ will be even because $\text{odd} + \text{odd} = \text{even}$. This continues and so every third Fibonacci will be even, and all others are odd.

Now that we know every third Fibonacci number is even, can we find a recurrence relation for just the even Fibonacci numbers? So we want to compute $F_n$ using $F_{n-3}$, $F_{n-6}$, $F_{n-9}$, etc.

We can start by writing out

and using this we can obtain a recurrence relation for $F_{n+6}$

So knowing that $F_3 = 2$ and $F_6 = 8$ we can use the recurrence relation

to generate all the even Fibonacci numbers directly, skipping over all the odd ones!

The even Fibonacci numbers $0, 2, 8, 34, 144, 610, 2584, \dots$ are OEIS A014445, and the entry lists this same recurrence $a_n = 4a_{n-1} + a_{n-2}$ along with the generating function $2x / (1 - 4x - x^2)$. The sums of the even Fibonacci numbers, $2, 10, 44, 188, \dots$, are OEIS A099919.

We can implement this in Julia:

function sum_even_fibonacci(limit)
    limit < 2 && return 0
    limit < 8 && return 2

    a, b = 2, 8
    result = a + b

    while (c = 4b + a) ≤ limit
        result += c
        a, b = b, c
    end

    return result
end

Benchmarking sum_even_fibonacci(4 * 10^6) we get 4.537 ns, which is 3.89× faster than generating every Fibonacci number. There are three times fewer terms to generate, and no parity check on each one. Since the Fibonacci numbers grow exponentially, we can increase the limit to a much larger number and still compute the sum quickly. For example, benchmarking sum_even_fibonacci(4 * 10^15) only takes 7.880 ns, which is 4.84× faster than the naive approach.

This solution takes $\mathcal{O}(\log L)$ time because Fibonacci numbers grow exponentially, so only about $\log L$ terms are needed to reach the limit $L$.

Generalizing to every $k^\text{th}$ Fibonacci number

We got lucky twice here. Every third Fibonacci number is even, and those even Fibonacci numbers happen to satisfy a two-term recurrence of their own. Is that second bit of luck special to $3$, or does every $k^\text{th}$ Fibonacci number satisfy a recurrence like this?

The first bit of luck isn't luck at all. The even Fibonacci numbers are $F_3, F_6, F_9, \dots$ and they're even because they are multiples of $F_3 = 2$, which is an instance of a general divisibility property: whenever $m$ divides $n$, $F_m$ divides $F_n$. This follows from the stronger identity $\gcd(F_m, F_n) = F_{\gcd(m, n)}$. So every fourth Fibonacci number is a multiple of $F_4 = 3$, every fifth is a multiple of $F_5 = 5$, every sixth is a multiple of $F_6 = 8$, and so on. "Even" is just the $k = 3$ case of "divisible by $F_k$".

Now for the recurrence. We could grind through the same substitutions we did for $F_{n+6}$, but for a general $k$ it's much less painful to start from Binet's formula

where $\varphi = \frac{1 + \sqrt{5}}{2}$ is the golden ratio and $\psi = \frac{1 - \sqrt{5}}{2}$, the two roots of $x^2 - x - 1 = 0$. The only property of these two numbers we'll need is that their product is

so $\psi = -1/\varphi$ and $\varphi = -1/\psi$. Now we want a formula involving $F_{n-k}$ and $F_{n+k}$ so taking $k$ steps backwards or forwards means that

Putting the first two into Binet's formula we get

which we can rearrange to get

Similarly, the other two give $F_{n+k}$, and this time there's no sign to move around

Now adding the two of them, the $\varphi^n$ and $\psi^n$ terms group together

That leftover factor of $\varphi^k + \psi^k$ looks like it might be irrational, but it never is! Since $\varphi$ and $\psi$ are both roots of $x^2 - x - 1 = 0$, multiplying that through by $x^{k-2}$ gives $\varphi^k = \varphi^{k-1} + \varphi^{k-2}$ and the same for $\psi$, so the sums $\varphi^k + \psi^k$ obey the exact same recurrence the Fibonacci numbers do. They just start off somewhere else, at $\varphi^0 + \psi^0 = 2$ and $\varphi + \psi = 1$. These are the Lucas numbers $L_k$ (OEIS A000032)

so what we've derived is that every $k^\text{th}$ Fibonacci number does satisfy a two-term recurrence

with the Lucas number $L_k$ as the coefficient and a sign that flips:

The $k = 1$ row is just the Fibonacci recurrence we started with, and the $k = 3$ row is the $F_n = 4F_{n-3} + F_{n-6}$ we derived by hand, shifted along by three indices.

Summing every $k^\text{th}$ Fibonacci number

Since the subsequence we're summing has its own two-term recurrence, let's give it its own name. Let's write $U_j = F_{kj}$ so that $U_0 = 0$ and $U_1 = F_k$, and the recurrence above becomes

We want to compute $\displaystyle S_m = \sum_{j=1}^m U_j$ so let's sum the recurrence itself from $j = 1$ to $m$ to get

We can rewrite each sum here as

Substituting these in we get

which allows us to solve for $S_m$ to get

We can now write a closed form for the sum of every $k^\text{th}$ Fibonacci number

This is a classical result (Koshy, 2001, Corollary 5.6, p. 86), and the denominators $L_k - (-1)^k - 1 = 1, 1, 4, 5, 11, 16, \dots$ are the associated Mersenne numbers (OEIS A001350). For $k = 1$ we have $L_1 = 1$ and recover the classic identity for the sum of all the Fibonacci numbers

And for $k = 3$ we have $L_3 = 4$ giving a closed form for the sum we actually care about

The largest even Fibonacci number not exceeding four million is $F_{33}$ and the next one is $F_{36}$, so the answer is

It's not like we needed a closed-form solution to solve the problem in a reasonable amount of time, but it's cool that we can derive something like this!

While writing this post I made a few small contributions to the OEIS. I submitted a short proof there that the sums of every $k^\text{th}$ Fibonacci number satisfy a recurrence of their own, using the same trick of summing a recurrence that we used above. I also submitted the closed form for these sums to A001350, since its terms are the denominators.

References