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
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.
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:
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:
, 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: