Problem 2: Even Fibonacci Numbers

Problem

• Link to the problem

Notes

The fibonacci numbers are $a_0=0$, $a_1=1$, $a_{n+2}=a_{n+1}+a_n$ for $n\ge 0$. We have:

$$\begin{array}{rlrl}{a}_0& =0& & \\ a_1& =1& & \\ a_2=a_1+a_0& =1& & \\ a_3=a_2+a_1& =2& & \\ a_4=a_3+a_2& =3& & \\ a_5=a_4+a_3& =5& & \end{array}\text{\hspace{1em}(even)(odd)(odd)(even)(odd)(odd)}$$

Claim: For all $k\ge 0$, $a_{3k}$ is even and $a_{3k+1}$, $a_{3k+2}$ are odd.

Proof by induction:

Base case: $k=0$

• $a_0=0$ (even) ✓
• $a_1=1$ (odd) ✓
• $a_2=1$ (odd) ✓

Inductive step: Assume the claim holds for some $k\ge 0$. We prove it for $k+1$.

By the inductive hypothesis:

• $a_{3k}$ is even
• $a_{3k+1}$ is odd
• $a_{3k+2}$ is odd

We need to show:

• $a_{3(k+1)}=a_{3k+3}$ is even
• $a_{3(k+1)+1}=a_{3k+4}$ is odd
• $a_{3(k+1)+2}=a_{3k+5}$ is odd

Using the Fibonacci recurrence:

$$a_{3k+3}=a_{3k+2}+a_{3k+1}=\text{odd}+\text{odd}=\text{even}$$

$$a_{3k+4}=a_{3k+3}+a_{3k+2}=\text{even}+\text{odd}=\text{odd}$$

$$a_{3k+5}=a_{3k+4}+a_{3k+3}=\text{odd}+\text{even}=\text{odd}$$

Therefore, the claim holds for $k+1$, completing the induction. $■$

Solution

See it on GitHub.

//* Problem 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.

//! time complexity: O(log n)
//! where n is the maximum value
// see the book for implementation details
// https://euler.newty.dev/problems/2.html#notes
use euler::prelude::*;

const MAX: u32 = 4_000_000;

fn solve() -> Solution {
    // every third fibonacci number is even.
    let mut sum = 0;
    let (mut a, mut b) = (2, 8);

    while a <= MAX {
        sum += a;
        (a, b) = (b, 4 * b + a);
    }

    solution!(sum)
}

problem!(
    2,
    solve,
    "1f5882e19314ac13acca52ad5503184b3cb1fd8dbeea82e0979d799af2361704"
);