I was fiddling around on Project Euler the other day, and looked back at one of the earlier problems (I think it was #2), which asks the following (I'm paraphrasing here): Find the sum of all those Fibonacci numbers that are both even and less than or equal to 4,000,000. Now, solving this iteratively is actually pretty simple, but I wanted to have a little fun and see if I could find a closed-form solution. So, in response to a friend who asked that I describe the solution, here it is:
First, we start with a definition. The sequence of Fibonacci numbers is described as a sequence such that any number in the sequence is equal to the sum of the previous two numbers. In other words, it satisfies the recurrence relation:
Let's look at some small terms of the Fibonacci sequence to get a feel for it:
We can notice straightaway that every 3rd number in the sequence appears to be even, but none of the rest are. In fact this is easy to prove - the Fibonacci sequence (from 1, anyway) starts with two odd numbers (1s). Now we note that for any place in the sequence, the nth number is the sum of the (n-1)th number and the (n-2)th number. If both of those numbers are odd, then the nth number will be even. If one is even, and one is odd, the nth number will be odd. Given those facts, we can see that the 3rd number will be the sum of two odd numbers and therefore even (2), the 4th will be the sum of an odd and an even, giving an odd (3), and the 5th will be the sum of an even and an odd, giving another odd (5) and resetting the proverbial counter. Thus, only every 3rd Fibonacci number is even - so those are the only ones we want to pay attention to. Let's give them a name: will hereafter denote the nth even Fibonacci number, and as discussed it has the formula:
Now let's see if we can turn this into a recurrence by stating it in terms of itself, as opposed to terms of the Fibonacci sequence. First, let's unfold on the right a few times and see what happens:
OK, hold it. Now it's time to notice something handy:
Given the above, we can now state our current unfolding as:
Let's continue unfolding again.
Stop! We have another term, as well as an term. Similar to the above equality, we can say that:
Leaving us with:
Now we just notice that, by definition:
Which leaves us with our final recurrence relation:
Now we can get to the real work. The first step is to take this relation and make it valid for all values of n. To do that, we'll use a Kronecker Delta, which looks like . This is just a handy little notation, the equivalent of a ternary conditional for math: if , then . Otherwise, . Using this logic, we can state the above recurrence as:
I should note here that is presumed to be 0 when . Thus, we can say the above is valid for all , as opposed to . When , the first two terms sum to 0, and the Kronecker delta spits out a 1, which is multiplied by 2 giving us an answer of 2. For all other values of n, the delta spits out a 0 and that whole term can be ignored. Neat!
Now comes the tricky part that is less than intuitive. We're going to solve this recurrence by means of an Ordinary generating function, or OGF. If you are unfamiliar with OGFs or generating functions in general, this may seem a bit like magic, but the upshot is that they're little machines that crank out a sequence of numbers, and can be represented in the form:
...where is used to denote the "coefficient of in A(z)". Now, looking at this sum, we can see that it looks a hell of a lot like the Taylor series expansion centered at 0 (in that case, also called the MacLaurin series) of any continuous function :
And, in fact, we can see that for OGFs:
Moving on, GFs in general typically have ridiculously simple closed forms - for instance, let's look at a really simple one. The following OGF generates the sequence :
Here, , and its closed form is:
OGFs have their own flavors of operations that can be performed on them, but they're far too dense a topic for me to cover in entirety here - if interested, I recommend you to Graham, Knuth, and Patashnik's fantastic (and entertaining!) textbook, Concrete Mathematics.
Anyway, moving on, the next step in solving our recurrence is to turn it into a function of generating functions, which we can then combine. First thing we'll do is multiply both sides by .
Now, we sum both sides on n from 0 to infinity:
Now, by the basic operations on OGFs, we know that multiplying an OGF by z shifts the whole sequence to the right - so we can restate the above as:
Additionally, since that last term is only ever 2 when and 0 otherwise, it is equivalent to , and we can trash the other notation.
Now we can clean things up further by using the notation:
Leading us to the much-easier-to-read:
Now we just need to solve for !
Woot! Now let's factor that polynomial in the denominator and get something even sexier! The roots of the polynomial are and (I'll leave this to you to verify on your own), and for conciseness we'll define these values as two constants:
This means we can represent the above as:
We can further clean up by using partial fractions to represent the remaining fraction:
Cross-multiplying and simplifying the above leaves us with two equations that and must satisfy:
These two linear equations of two variables can be solved pretty simply, leaving us with the following values for and :
Substituting these constants into the partial fraction gives us:
Which we then subtitute back into the original equation as:
Now we can state this whole thing in terms of known OGFs and operations thereupon!
Now, we have the following truth (we can ignore because it is defined as 0):
This in turn implies that:
We now have our closed-form solution for the nth even Fibonacci number! Let's try it out!
What about for ?
Looks pretty good! Now that we have a closed-form solution for the sequence of even Fibonacci numbers, we are asked to find the sum over all less than 4,000,000. The first step therein is to find the value m for which is less than or equal to 4,000,000. First we generalize to find the value m for which is less than or equal to some max value So we write the following inequality and solve for m (as a floored integer):
Since we're taking the floor of the result, and for all positive values of m, we can safely ignore that term:
Now that we know how to find given , What we need to answer the question is to find the following:
Oh no! Not another freakin' sum! Luckily, this can be tidied away quite simply itself!
We can kerjigger these two sums a bit by shifting indices, popping off the top term, and subtracting one from each:
Now, because both and are constants, these evaluate to simple geometric series for which we have closed forms!
While I'm not going to go through all the steps here, you can simplify this down to our final formula for , the sum of all even Fibonacci numbers less than or equal to :
Now, plugging 4,000,000 into returns 11. So, replacing all instances of with 11 in the formula for yields us our final answer: