Euler #2: Even Fibonacci Numbers

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.

https://projecteuler.net/problem=2

Much ado has been made about the Fibonacci sequence. It is ubiquitous in nature, from rabbit breeding rates to sunflower seed arrangements. Artists love to exploit it for their compositions. It pops up in surprising places such as optical reflections, economics, and music.

Its ubiquity perhaps can be explained by the sequence’s relationship to the Golden Ratio, represented by \varphi. Take two positive numbers a and b. If their ratio is the same as the ratio of their sum to the larger number, they are in the Golden Ratio.

\varphi:=\frac{a+b}{a}=\frac{a}{b}

We can rearrange the left fraction to get an equation that is in terms of only \varphi.

\varphi=\frac{a+b}{a}=\frac{a}{a}+\frac{b}{a}=1+\frac{1}{\varphi}

Solving for \varphi yields the quadratic equation \varphi^2 - \varphi - 1 = 0. Plugging and chugging with the Quadratic Formula gives

\varphi=\frac{1+\sqrt{5}}{2}\approx1.618...

The Golden Ratio and the Fibonacci sequence are connected to one other by way of Binet’s Formula. In fact, it gives the nth term of the Fibonacci sequence, F_n, using only \varphi and n! (factorial unintended)

F_n=\frac{\varphi^n-(-\varphi)^{-n}}{\sqrt{5}} \tag{1}

This formula will come in handy for the solution. However, the solution is asking for only even Fibonacci numbers. How do we sum up only the even F_n? We know that adding two odd numbers will always give an even number. Adding an odd and even number will always give an odd number.

We see that even Fibonacci numbers occur when n is a multiple of 3. We can start setting up the summation to “skip” over odd F_n.

\text{solution}=\sum_{i=1}^{?}F_{3i}

All that remains is to figure out the upper bound of summation. The problem is asking for the sum of even F_n that do not exceed four million. This means that we need to find the largest n such that F_n < 4000000. This is easy to do with Binet’s Formula by trying random n. Trial and error gives n=33. F_{33} is 3524578, which is even. Since we’re multiplying the index of summation by 3, the upper bound of summation is 33/3=11. We have a complete equation ready for some algebraic maneuvering!

\text{solution}=\sum_{i=1}^{11}F_{3i}=\sum_{i=1}^{11}\frac{\varphi^{3i}-(-\varphi)^{-{3i}}}{\sqrt{5}}

We factor out the denominator and split the summation into two terms:

\text{solution}=\frac{1}{\sqrt{5}} \Bigg( \sum_{i=1}^{11}{\varphi^{3i}}-\sum_{i=1}^{11}{(-\varphi})^{-3i} \Bigg) \tag{2}

These two sums are geometric sums, which have the general solution:

\sum_{i=1}^{N}c^i=\frac{c^{N+1}-1}{c-1}-1 \tag{3}

Since \varphi^{3i} and (-\varphi)^{-3i} can be rewritten as (\varphi^3)^i and (-\varphi^{-3})^i respectively, our equation crumbles at the might of geometric sums and yields a closed form that any calculator can make short work of.

Before we can use Equation 3 to simplify Equation 2, we need to rewrite Equation 2’s summands so that they are of the form c^i:

\text{solution}=\frac{1}{\sqrt{5}} \Bigg( \sum_{i=1}^{11}{(\varphi^{3})^i}-\sum_{i=1}^{11}{((-\varphi})^{-3})^i \Bigg) \tag{4}

Now we can plug and chug with the help of Equation 3!

\text{solution}=\frac{1}{\sqrt{5}} \Bigg( \Big[ \frac{(\varphi^{3})^{12}-1}{(\varphi^{3})-1}-1 \Big] - \Big[ \frac{(-\varphi^{-3})^{12}-1}{(-\varphi^{-3})-1} -1 \Big] \Bigg)

Admittedly, that’s one beast of an equation and a chore to punch into the hapless calculator. It’s best to break it up by making judicious use of the STO function. The calculator gives 4613732. Now, of course, all this arithmetic pales in the sheer efficiency of computers. The Python solution is easy:

fib = [0, 1]
for i in range(2, 34):
    fib.append(fib[i-1] + fib[i-2])
sum([even_fib for even_fib in fib if even_fib % 2 == 0])