Efficient Computation of Finite, Even-Valued Fibonacci Sums using Fast Doubling

Basic Useful Properties

The nth term of the Fibonacci sequence \(\langle F_n\rangle\) is given by \[ F_n = \begin{cases} 0 & \text{if} \,\, n=0 \\ 1 & \text{if} \,\, n=1 \\ F_{n-2} + F_{n-1} & \text{if} \,\, n > 2 \end{cases} \]

Alternatively, in matrix form \[ \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} \]

The sequence begins as \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...\) For large values of \(n\), the computation of \(F_n\) can be expensive. Thus, it is necessary to become familiar with some useful identities.

\[ \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}^{n} = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} \]

This equation is readily proven through mathematical induction, and can also provide the next useful identity

\[ \begin{aligned} F_{2n+1} &= F_{n+1}^2 + F_n^2 \\ F_{2n} &= F_n[F_{n+1} + F_{n-1}] \end{aligned} \]

Therefore, if \(F_n\) and \(F_{n+1}\) are known, we have a means to easily compute \(F_{2n}\) and \(F_{2n+1}\). The second equation may also be written \[ F_{2n}=F_n[2F_{n+1}-F_n] \]

which is easy to show \[ \begin{aligned} &F_n := F_{n+1} - F_{n-1} \\ \iff F_{n+1} + &F_n = 2F_{n+1} - F_{n-1} \\ \iff F_{n+1} + &F_{n-1} = 2F_{n+1} - F_n \end{aligned} \]

The following program makes use of the efficiency implied by these identities.

def fibonacci(n):
    if n < 0:
        assert ValueError("Negative arguments not imlemented")
    else:
        return _fib(n)[0]

def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

Fibonacci Sums

If we wish to sum the first \(n\) terms the following holds for all positive integers \(n\): \[ \sum_{i=1}^nF_i = F_{n+2} - 1 \] and to sum the first \(n\) even Fibonacci values: \[ \sum_{i=1}^nF_{2i} = F_{2n+1} - 1 \]

To give confidence in the second sum provided above I supply a simple proof by mathematical induction.

In the base case we let \(n=1\) so that \(F_2 = F_3 - 1 = 2 - 1 = 1\) is verified.

Assume that \(\sum_{i=1}^nF_{2i} = F_{2n+1} - 1\)

Then \[ \begin{aligned} \sum_{i=1}^{n+1}F_{2i} &= \sum_{i=1}^nF_{2i} + F_{2n+2} \\ &= F_{2n+1} + F_{2n+2} - 1 & (\text{by assumption}) \\ &= F_{2n+3} - 1 & (\text{by definition}) \\ &= F_{2(n+1)+1} - 1 \\ & & \blacksquare \end{aligned} \]

Nearest Fibonacci Number Less Than Another Integer

To find the nearest Fibonacci number less than some integer we can find the index \(n\) satisying \[ \text{arg} \max_{n} F_n < N \] for some \(N \in \mathbb{Z}^+\)

Since \(F_n\) satisfies the definition of a constant-recursive sequence it may be expressed in closed form according to Binet’s formula \[ F_n := \frac{\phi^n - \psi^n}{\sqrt5} \] where \[ \phi = \frac{1+\sqrt5}{2}, \quad\quad \psi=\frac{1-\sqrt5}{2} \] Now \(|\psi| < 1 \implies |\psi^n|<1\) for \(n\geq1\)

and so we have that \[ \bigg|F_n - \frac{\phi^n}{\sqrt5}\bigg| = \bigg|\frac{\psi^n}{\sqrt5}\bigg| < \frac{1}{\sqrt5} \] \(\implies F_n\) must be the closest integer to \(\frac{\phi^n}{\sqrt5}\) for all \(n\geq 1\).

Finally, given such an \(N\) we can find \[ \text{arg} \max_{n} \phi^n < \sqrt5 N \\ \equiv \text{arg} \max_{n} n < \frac{log(\sqrt5N)}{log\phi} \\ = \bigg\lfloor \frac{log(\sqrt5N)}{log\phi} \bigg\rfloor \]

import numpy as np
# using Binet's formula
def nearest_term(N):
    return np.floor(np.log(np.sqrt(5)*N) / np.log((1+np.sqrt(5)) / 2))

To find \(n\) such that \(F_n < 4\times10^6\) for example:

nearest_term(4000000)

33.0

Then using the identity erived for summing even valued Fibonacci numbers up to \(n\), where \(n=3m\) \[ \sum_{k=1}^{10} F_{3k} = \frac{F_{34}+F_{33}-1}{2} \]

# computing solution to above
(fibonacci(34) + fibonacci(33) - 1) / 2

4613732.0

Therefore the total sum of even-valued Fibonacci numbers less than 4 million is 4613732.