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.