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