# Summing the Fibonacci Sequence

An image from nature (by Sustainable San Mateo). The golden ratio approximately (this is a topic for discussion) appears in here and is closely related to 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 $f(n)$ be the $n^{th}$ element in the Fibonacci sequence (where $n$ is an integer, starting from $0$). Define $f(0)=0$, $f(1)=1$ and now the Fibonacci sequence follows by the given rule: $f(n+2)=f(n+1)+f(n)$. For example, $f(2)=f(1)+f(0)=1+0=1$, $f(3)=f(2)+f(1)=1+1=2$, $f(4)=f(3)+f(2)=2+1=3$ and a last example: $f(5)=f(4)+f(3)=3+2=5$, so we indeed get the sequence $0, 1, 1, 2, 3, 5, ...$. Note the starting $0$. 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 $E$ as the event that a number is an even number and let’s denote $O$ as the event that a number is an odd number. Now $OO$ means that the first number is odd and also the second number is odd. The four possible scenario’s are: $OO, EO, OE$ and $EE$. The Fibonacci sequence adds up the two previous numbers. So suppose we have an odd number and another odd number. An odd number $m$ can be represented as follows: $m = 2n + 1$ for an integer $n$. Adding two odd numbers, $m_1$ and $m_2$ gives an even number: $m_1 = 2n_1 + 1$, $m_2 = 2n_2 + 1$, so $m_1 + m_2 = 2(n_1 + n_2) + 2 = 2(n_1 + n_2 + 1)$. So next event after an $OO$ sequence is an $E$. We can do similar calculations for the other events:

$OO \Rightarrow E$ $OE \Rightarrow O$ $EO \Rightarrow O$ $EE \Rightarrow E$

We start with $EO$ ($f(0)=0, f(1)=1$). So according to the rules above, the next one is $O$ ($f(2)=1$) and the one thereafter should be even ($OO \Rightarrow E$, and indeed, $f(3)=2$ is even). So $EO \Rightarrow OE$. Where will $OE$ result into? $OE \Rightarrow O$ and $EO \Rightarrow O$, so $OE \Rightarrow OO$. The total chain so far is $EO \Rightarrow OE \Rightarrow OO$. The next then is $E$ ($OO \Rightarrow E$) and the one thereafter is $O$, so the next in line is $EO$ which is also equal to the start of our chain! So the complete chain is the following:

$EO \Rightarrow OE \Rightarrow OO \Rightarrow EO$

So, to summarize, after every 6 numbers, the chain is repeated. For every chain (if we start counting on $0$), then the $0^{th}$ and the $3^{th}$ number are even (and after that the $6^{th}$ and the $9^{th}$ number, and so on). That can be simplified further! All $n^{th}$ numbers where $n$ is an integer and divisible by $3$ are even! Let’s verify that! $f(0)=0$ which is even, $f(3)=2$ (even), $f(6)=8$ (even), $f(9)=34$ (even) and so on. The beauty here is that it holds for all numbers in the sequence: $f(3n)$ is even for every integer $n$ greater or equal than $0$.

Our mission was to sum up all even numbers from the Fibonacci sequence, so this now boils down to $f(0)+f(3)+f(6)+... = \sum\limits_{n=0}^{n_{max}} f(3n)$

## 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 $x$ that satisfies the following requirement:

$x^n=f(n)$

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

$f(n+2)=f(n+1)+f(n) \Rightarrow x^{n+2} = x^{n+1} + x^n$

This can be rewritten as follows:

$x^n(x^2 + x + 1)=0$

Interesting! Note the polynomial factor. Let’s define $r(x)=x^2+x+1$ to simplify the above expression to $x^n r(x) = 0$. After doing some basic math, we can find the solution for $x^2+x+1$, namely $x_1 = \frac{1}{2} + \frac{1}{2} \sqrt{5}$ and $x_2 = \frac{1}{2} - \frac{1}{2} \sqrt{5}$. So both $x_1^n$ and $x_2^n$ are solutions for our problem. In other words, both $f(n)=x_1^n$ and $f(n)=x_2^n$ hold. But notice the following: we can modify our initial equation as follows:



That mean that if $q^n$ is a solution to the problem, then $\alpha q^n$ is also a solution to the problem. And also notice the following: suppose that $u^n$ and $v^n$ are solutions to the problem. Then $u^n + v^n$ are also solutions to the problem. In general, if $u^n$ and $v^n$ are solutions to the problem, then $c u^n + d v^n$ are solutions to the problem.

Now we have a little more information! We know that $x_1$ and $x_2$ are solutions to the problem, so we know that $c x_1^n + d x_2^n$ is a solution to the problem for any real numbers $c$ and $d$. Since $f(0)=0$ we can derive the following:

$f(0)=0 \Rightarrow cx_1^0 + dx_2^0 = c + d = 0 \Rightarrow d = -c$

Next equation: $f(1)=1$ gives the following insight:

$f(1)=1 \Rightarrow cx_1 + dx_2 = 1 \Rightarrow c x_1 - cx_2 = 1 \Rightarrow c = \frac{1}{x_1 - x_2}$

Et voila! $c = \frac{1}{x_1 - x_2}$ and $d = -c = -\frac{1}{x_1 - x_2}$

This also solves the overall formula:

$f(n) = c x_1^n + d x_2^n = \frac{x_1^n - x_2^n}{x_1 - x_2} = \frac{(\frac{1}{2} + \frac{1}{2} \sqrt{5})^n - (\frac{1}{2} - \frac{1}{2} \sqrt{5})^n}{\sqrt{5}}$

What a monster! Let’s try out for $f(2)$ for which we know that $f(2)=f(1)+f(0)=1+0=1$:

$f(2) =\frac{(\frac{1}{2} + \frac{1}{2} \sqrt{5})^2 - (\frac{1}{2} - \frac{1}{2} \sqrt{5})^2}{\sqrt{5}} = \frac{\frac{1}{4} + \frac{5}{4} + \frac{1}{2}\sqrt{5} - \frac{1}{4} + \frac{1}{2}\sqrt{5} - \frac{5}{4}}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}} = 1$

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 $f(34)=5702887$. So $n=33$ is the $n$ such that its element in the Fibonacci sequence is the largest which does not exceed 4 million. Since it is a multiple of $3$, it even simplifies our problem. We want to sum up all even numbers of the Fibonacci sequence and remember that these are the elements $f(3n)$ for any integer $n$. So we seek $f(0) + f(3) + f(6) + ... + f(33)$. In other words, we seek $\sum\limits_{n=0}^{11} f(3n)$. By our beautiful equivalent of $f(n)$ found earlier, we know that this equals:

$\sum\limits_{n=0}^{11} f(3n) =\sum\limits_{n=0}^{11} f(3n) =\sum\limits_{n=0}^{11} \frac{x_1^{3n} - x_2^{3n}}{x_1 - x_2}$

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

$\sum\limits_{n=0}^{11} f(3n) =\sum\limits_{n=0}^{11} \frac{x_1^{3n} - x_2^{3n}}{x_1 - x_2}=\frac{1}{x_1 - x_2} \sum\limits_{n=0}^{11} x_1^{3n} - x_2^{3n}$

We can also split the sum:

$\frac{1}{x_1 - x_2} ( \sum\limits_{n=0}^{11} x_1^{3n} - x_2^{3n}) =\frac{1}{x_1 - x_2}\sum\limits_{n=0}^{11} x_1^{3n} -\frac{1}{x_1 - x_2} \sum\limits_{n=0}^{11} x_2^{3n}$

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

## Solve $\sum\limits_{n=0}^m a^{kn}$

So, we first start with a definition. Let $a$ be a real number (warning: I actually have very strict about $a$, but I will do it less strict here). Let $k$ be a real number and let $m$ be an integer larger or equal than 0. Define:

$s = \sum\limits_{n=0}^m a^{kn}$

Then:

$a^k \cdot s = a^k \cdot \sum\limits_{n=0}^m a^{kn} = \sum\limits_{n=0}^m a^{k{n+1}} = \sum\limits_{n=1}^{m+1} a^{kn}$

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

$a^k \cdot s - s = s(a^k - 1) = a^{k{m + 1}} - 1 \Rightarrow s = \frac{a^{k{m+1}}-1}{a^k - 1}$

Cool! Problem solved.

## Putting all the parts together

We need to compute $\sum\limits_{n=0}^{11} x_1^{3n} -\sum\limits_{n=0}^{11} x_2^{3n}$ and we know have the tool to do so!



Now we can fill in the found numbers for $x_1$ and $x_2$:



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

$4613732$

## Conclusion (TL;DR)

$4613732$, 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))

#### Kevin Jacobs

Kevin Jacobs is a certified Data Scientist and blog writer for Data Blogger. He is passionate about any project that involves large amounts of data and statistical data analysis. Kevin can be reached using Twitter (@kmjjacobs), LinkedIn or via e-mail: mail@kevinjacobs.nl.