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:

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

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 $f(33) = 3524578$ 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!

$\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 $x_1$ and $x_2$:

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

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