# Summing the Fibonacci Sequence

Consider the following problem (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, …

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

Solving this problem by using a programming language is relatively easy and requires only looping through the sequence. How can you tackle this problem without the need for a computer? Spoiler alert: there is only one final step in which we will use a calculator.

## Defining the problem, mathematically

Let’s define the Fibonacci sequence mathematically. Let

be the

element in the Fibonacci sequence (where

is an integer, starting from

). Define

,

and now the Fibonacci sequence follows by the given rule:

. For example,

,

,

and a last example:

, so we indeed get the sequence

. Note the starting

. This is different than the sequence above, but it will not do any harm!

## Sequence: spotting odd/even numbers

We are looking for even numbers in the given sequence. How can we find these? Notice that there are four possible scenario’s for two consequent numbers. Let’s denote

as the event that a number is an even number and let’s denote

as the event that a number is an odd number. Now

means that the first number is odd and also the second number is odd. The four possible scenario’s are:

and

. The Fibonacci sequence adds up the two previous numbers. So suppose we have an odd number and another odd number. An odd number

can be represented as follows:

for an integer

and

gives an even number:

,

, so

. So next event after an

sequence is an

. We can do similar calculations for the other events:

(

). So according to the rules above, the next one is

(

) and the one thereafter should be even (

, and indeed,

is even). So

. Where will

result into?

and

, so

. The total chain so far is

. The next then is

(

) and the one thereafter is

, so the next in line is

which is also equal to the start of our chain! So the complete chain is the following:

So, to summarize, after every 6 numbers, the chain is repeated. For every chain (if we start counting on

), then the

and the

number are even (and after that the

and the

number, and so on). That can be simplified further! All

numbers where

is an integer and divisible by

are even! Let’s verify that!

which is even,

(even),

(even),

(even) and so on. The beauty here is that it holds for all numbers in the sequence:

is even for every integer

greater or equal than

.

Our mission was to sum up all even numbers from the Fibonacci sequence, so this now boils down to

## Recurrecurrecurrecurre… (recurrence)

I can elaborate many lines on this, but I try to keep it short. Next step is to convert this problem into another problem for which we know the solution.

We try to find an

that satisfies the following requirement:

Does this

exists and if so, how does it look like? Let’s try to plug it in into the formula for the Fibonacci sequence:

This can be rewritten as follows:

Interesting! Note the polynomial factor. Let’s define

to simplify the above expression to

. After doing some basic math, we can find the solution for

, namely

and

. So both

and

are solutions for our problem. In other words, both

and

hold. But notice the following: we can modify our initial equation as follows:

That mean that if

is a solution to the problem, then

is also a solution to the problem. And also notice the following: suppose that

and

are solutions to the problem. Then

are also solutions to the problem. In general, if

and

are solutions to the problem, then

are solutions to the problem.

and

are solutions to the problem, so we know that

is a solution to the problem for any real numbers

and

. Since

we can derive the following:

Next equation:

gives the following insight:

Et voila!

and

This also solves the overall formula:

What a monster! Let’s try out for

for which we know that

:

What a beauty!

## Back to the summing

So, we were asked to sum all even numbers in the Fibonacci sequence up to some number. Okay, I have to admit that this is the only point where I use a computer. It is asked to consider only the terms in the Fibonacci sequence that do not exceed 4 million. A quick check on the computer gives me that

which is slightly less than 4 million and

. So

is the

such that its element in the Fibonacci sequence is the largest which does not exceed 4 million. Since it is a multiple of

, it even simplifies our problem. We want to sum up all even numbers of the Fibonacci sequence and remember that these are the elements

for any integer

. So we seek

. In other words, we seek

. By our beautiful equivalent of

found earlier, we know that this equals:

Don’t be scared! We can simplify this down further:

We can also split the sum:

And now we only need to know how we can calculate these sums easily.

## Solve

be a real number (warning: I actually have very strict about

, but I will do it less strict here). Let

be a real number and let

be an integer larger or equal than 0. Define:

Then:

And now subtract the two to cancel out a lot of common terms:

Cool! Problem solved.

## Putting all the parts together

We need to compute

and we know have the tool to do so!

Now we can fill in the found numbers for

and

:

And with a calculator (actually by using Scala) we now can find the answer to the original question:

## Conclusion (TL;DR)

, and do not use math here. It gives beautiful results and generalize results, but a simple functional programming approach (by brute forcing all numbers) would have been way faster to solve this problem:

/**
* Calculate the nth Fibonacci number.
*
* @param n index in the sequence
* @return nth Fibonacci number
*/
def fibonacci(n: Int): Int = {
if (n == 0) return 0
if (n == 1) return 1
fibonacci(n - 1) + fibonacci(n - 2)
}

/**
* Calculate the sum of even Fibonacci numbers which do not exceed m.
*
* @param m upper bound
* @param k current index to try out
* @return sum of even Fibonacci numbers up to m
*/
def sum(m: Int, k: Int): Int = {
// Calculate the kth Fibonacci number
val f = fibonacci(k)
// If f does not exceed m and f is even, then give back f plus the sum of the remaining sequence
if (f < m && f % 2 == 0) return f + sum(m, k + 1)
// If f exceeds m, then there is no interesting result to be found
if (f >= m) return 0
// Otherwise, f is not even, so only sum over the remainder of the sequence
sum(m, k + 1)
}

println(sum(4000000, 0))