The second problem is: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Lets again start with a python script solving this:

from itertools import takewhile, filterfalse
def fib():
        lastfib = 1
        fib = 0
        tmp = 0
        while True:
                yield fib
                tmp = fib
                fib = lastfib + fib
                lastfib = tmp

print(sum(filterfalse(lambda x: x % 2, takewhile(lambda x: x<4000000, fib()))))

Analytically, I have not gotten far. First thing I notice is that \textrm{fib}\left(n\right) is only even if n \% 3 = 0 , else it is odd.

Think in binary or follow my proof if you do not believe me:

First step, \textrm{fib}\left(3 \cdot n\right) is always even:

Basis:

n = 0 \\\ \textrm{fib}\left(0\right) = 0

Assumption: Holds to n , therefore \textrm{fib}\left(n\right) is even

Induction: n \rightarrow n + 1

\begin{align} \textrm{fib}\left(3\cdot \left(n+1\right) \right) &= \textrm{fib}\left(3\cdot n + 3\right) \\\ &= \textrm{fib}\left(3 \cdot n + 2\right) + \textrm{fib}\left(3 \cdot n + 1\right) \\\ &= 2 \cdot \textrm{fib}\left(2 \cdot n + 1 \right) + \textrm{fib}\left(3 \cdot n \right) \end{align}

2 \cdot x, x \in N is always even, \textrm{fib}\left(3 \cdot n\right) is even and the sum of even numbers is even as well. Ergo \textrm{fib}\left(3 \cdot n\right) is always even!

But we still have to proof that \textrm{fib}\left(3 \cdot n\right) are the ONLY even numbers!

Lets take a look at \textrm{fib}\left(3 \cdot n + 2\right) which should be always odd:

Basis:

n = 0 \\\ \textrm{fib}\left(2\right) = 1

Assumption: Holds to n , therefore \textrm{fib}\left(n + 2\right) is odd

Induction: n \rightarrow n + 1

\begin{align} \textrm{fib}\left(3 \cdot \left(n+1\right) + 2\right) &= \textrm{fib}\left(3 \cdot n + 5\right) \\\ &= \textrm{fib}\left(3n + 4\right) + \textrm{fib}\left(3 \cdot \left(n + 1\right)\right) \\\ &= 2 \cdot \textrm{fib}\left(3 \cdot \left(n + 1\right)\right) + \textrm{fib}\left(3 \cdot n + 2\right) \end{align}

A sum of a odd and an even number is always odd hence \textrm{fib}\left(3 \cdot n+2\right) is odd

What is left? \textrm{fib}\left(3 \cdot n + 1\right) !

Basis:

n = 0 \\\ \textrm{fib}\left(1\right) = 1

Assumption: Holds to n , therefore \textrm{fib}\left(n + 1\right) is odd

Induction: n \rightarrow n + 1

\begin{align} \textrm{fib}\left(3 \cdot \left(n+1\right) + 1\right) &= \textrm{fib}\left(3 \cdot n + 4\right) \\\ &= \textrm{fib}\left(3 \cdot n + 2 \right) + \textrm{fib}\left(3 \cdot \left(n + 1\right)\right) \\\ \end{align}

And again, odd + even = odd!

So the only even numbers in the Fibonacci sequence are the ones with n \% 3 = 0 !

But that’s it, no idea how to battle this problem further.

Update

Well, after some thinking, I guess I found an analytic solution.

Lets have look which Fibonacci numbers are in the sum of all even Fibonacci numbers: (remember, every third is even)

\begin{array}{c|ccccccccccccc} N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\ 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\ \end{array}

But these could also be written like this: \begin{array}{c|ccccccccccccc} N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\ 2 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\\ 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\\ \end{array}

This means that \sum\_{i=0}^N f\_{\textrm{even}} = \sum\_{i=0}^N f\_{\textrm{odd}} and therefore we can also write it as: \sum\_{i=0}^N f\_{\textrm{even}} = \frac{1}{2} \sum\_{i=0}^N f\_i

We now only need to know what the sum of all Fibonacci numbers to some n is: \sum\_{i=0}^N f\_i = f\_{N+2} - 1

Wherefore, the solution is: \sum\_{i=0}^N f\_{\textrm{even}} = \frac{f\_{n+2} - 1}{2} \\ \textrm{with n chosen to be the biggest value fulfilling: } f\_n \leq 4000000