Problem 2: Even Fibonacci numbers

Problem:

Please find the problem here.

Solution:

Again, brute force worked great. Observe that Fibonacci numbers are growing exponentially, there are only a handful of terms before the sequence reach four million. Here is the code:

namespace Euler
{
    using System;

    internal static partial class Program
    {
        public static void Problem002()
        {
            int fib, fibLast, fibLastLast;
            fibLast = 1;
            fibLastLast = 1;
            int sum = 0;
            do
            {
                fib = fibLast + fibLastLast;
                if (fib % 2 == 0)
                {
                    sum += fib;
                }

                fibLastLast = fibLast;
                fibLast = fib;
            } while (fib < 4000000);
            Console.WriteLine(sum);
        }
    }
}

Again, we do have better method, which doesn't really worth the time. But for completeness sake, I will describe it here. First, observe that even valued Fibonacci numbers appear as every third element, there is an easy way to show this is exactly the case.

Proposition 1.1: $F_n$ is even if and only if $n = 2 \mod 3$.
Prove: Apparently, the proposition is true for small $n$, in particular, $n \le 3$. Assume the proposition is true for all $n \le k$, for $F_{k+1} = F_{k} + F_{k-1}$, we can deduce $F_k$ is even if and only if both $F_k$ and $F_{k-1}$ are both odd or both even. But they cannot be both even (by assumption), so $F_{k+1}$ is even if and only if $F_k$ and $F_{k-1}$ are both odd, that correspond to $k = 1 \mod 2$ and therefore the position also hold true for $n = k + 1$. By the principle of mathematical induction the proposition is true for all natural number $n$.

With the proposition above, we could avoid the division and just do the sum as follow, and it is guaranteed to give the same result.

namespace Euler
{
    using System;

    internal static partial class Program
    {
        public static void Problem002()
        {
            int fib, fibLast, fibLastLast;
            fibLast = 1;
            fibLastLast = 1;
            int sum = 0;
            int i = 0;
            do
            {
                fib = fibLast + fibLastLast;

                if (i == 0)
                {
                    sum += fib;
                }

                i++;
                if (i == 3)
                {
                    i = 0;
                }

                fibLastLast = fibLast;
                fibLast = fib;
            } while (fib < 4000000);

            Console.WriteLine(sum);
        }
    }
}

Answer: 4613732.