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

$latex OO \Rightarrow E$

$latex OE \Rightarrow O$

$latex EO \Rightarrow O$

$latex EE \Rightarrow E$

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

$latex 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 $latex 0$), then the $latex 0^{th}$ and the $latex 3^{th}$ number are even (and after that the $latex 6^{th}$ and the $latex 9^{th}$ number, and so on). That can be simplified further! All $latex n^{th}$ numbers where $latex n$ is an integer and divisible by $latex 3$ are even! Let’s verify that! $latex f(0)=0$ which is even, $latex f(3)=2$ (even), $latex f(6)=8$ (even), $latex f(9)=34$ (even) and so on. The beauty here is that it holds for all numbers in the sequence: $latex f(3n)$ is even for every integer $latex n$ greater or equal than $latex 0$.

Our mission was to sum up all even numbers from the Fibonacci sequence, so this now boils down to $latex 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 $latex x$ that satisfies the following requirement:

$latex x^n=f(n)$

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

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

This can be rewritten as follows:

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

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

$latex x^n(x^2 + x + 1)=0 \Rightarrow \alpha x^n(x^2 + x + 1) = \alpha \cdot 0 = 0$

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

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

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

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

$latex 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! $latex c = \frac{1}{x_1 – x_2}$ and $latex d = -c = -\frac{1}{x_1 – x_2}$

This also solves the overall formula:

$latex 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 $latex f(2)$ for which we know that $latex f(2)=f(1)+f(0)=1+0=1$:

$latex 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 $latex f(33) = 3524578$ which is slightly less than 4 million and $latex f(34)=5702887$. So $latex n=33$ is the $latex n$ such that its element in the Fibonacci sequence is the largest which does not exceed 4 million. Since it is a multiple of $latex 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 $latex f(3n)$ for any integer $latex n$. So we seek $latex f(0) + f(3) + f(6) + … + f(33)$. In other words, we seek $latex \sum\limits_{n=0}^{11} f(3n)$. By our beautiful equivalent of $latex f(n)$ found earlier, we know that this equals:

$latex \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:

$latex \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:

$latex \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 $latex \sum\limits_{n=0}^m a^{kn}$

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

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

Then:

$latex 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:

$latex 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 $latex \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!

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

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

$latex \frac{1}{x_1 – x_2} (\frac{x_1^{36} – 1}{x_1^3 – 1} -\frac{x_2^{36} – 1}{x_2^3 – 1}) = \frac{1}{\sqrt{5}} (\frac{(\frac{1}{2} + \frac{1}{2} \sqrt{5})^{36} – 1}{(\frac{1}{2} + \frac{1}{2} \sqrt{5})^3 – 1} -\frac{(\frac{1}{2} – \frac{1}{2} \sqrt{5})^{36} – 1}{(\frac{1}{2} – \frac{1}{2} \sqrt{5})^3 – 1}) $

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

$latex 4613732$

## Conclusion (TL;DR)

$latex 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: