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
. Adding two odd numbers,
and
gives an even number:
,
, so
. So next event after an
sequence is an
. We can do similar calculations for the other events:
We start with
(
). 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.
Now we have a little more information! We know that
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
So, we first start with a definition. Let
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))