Mathematics

Summing the Fibonacci Sequence

Kevin Jacobs

• 12 min read
Summing the Fibonacci Sequence
Photo by Ludde Lorentz / Unsplash

Consider the following problem (Project Euler, Problem #2):

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.

Solving this problem by using a programming language is relatively easy and requires only looping through the sequence. How can you tackle this problem without the need for a computer? Spoiler alert: there is only one final step in which we will use a calculator.

Defining the problem, mathematically

Let’s define the Fibonacci sequence mathematically. Let

f(n)

be the

n^{th}

element in the Fibonacci sequence (where

n

is an integer, starting from

0

). Define

f(0)=0

,

f(1)=1

and now the Fibonacci sequence follows by the given rule:

f(n+2)=f(n+1)+f(n)

. For example,

f(2)=f(1)+f(0)=1+0=1

,

f(3)=f(2)+f(1)=1+1=2

,

f(4)=f(3)+f(2)=2+1=3

and a last example:

f(5)=f(4)+f(3)=3+2=5

, so we indeed get the sequence

0, 1, 1, 2, 3, 5, …

. Note the starting

0

. This is different than the sequence above, but it will not do any harm!

Sequence: spotting odd/even numbers

We are looking for even numbers in the given sequence. How can we find these? Notice that there are four possible scenario’s for two consequent numbers. Let’s denote

E

as the event that a number is an even number and let’s denote

O

as the event that a number is an odd number. Now

OO

means that the first number is odd and also the second number is odd. The four possible scenario’s are:

OO, EO, OE

and

EE

. The Fibonacci sequence adds up the two previous numbers. So suppose we have an odd number and another odd number. An odd number

m

can be represented as follows:

m = 2n + 1

for an integer

n

. Adding two odd numbers,

m_1

and

m_2

gives an even number:

m_1 = 2n_1 + 1

,

m_2 = 2n_2 + 1

, so

m_1 + m_2 = 2(n_1 + n_2) + 2 = 2(n_1 + n_2 + 1)

. So next event after an

OO

sequence is an

E

. We can do similar calculations for the other events:

OO \Rightarrow E
OE \Rightarrow O
EO \Rightarrow O
EE \Rightarrow E

We start with

EO

(

f(0)=0, f(1)=1

). So according to the rules above, the next one is

O

(

f(2)=1

) and the one thereafter should be even (

OO \Rightarrow E

, and indeed,

f(3)=2

is even). So

EO \Rightarrow OE

. Where will

OE

result into?

OE \Rightarrow O

and

EO \Rightarrow O

, so

OE \Rightarrow OO

. The total chain so far is

EO \Rightarrow OE \Rightarrow OO

. The next then is

E

(

OO \Rightarrow E

) and the one thereafter is

O

, so the next in line is

EO

which is also equal to the start of our chain! So the complete chain is the following:

EO \Rightarrow OE \Rightarrow OO \Rightarrow EO

So, to summarize, after every 6 numbers, the chain is repeated. For every chain (if we start counting on

0

), then the

0^{th}

and the

3^{th}

number are even (and after that the

6^{th}

and the

9^{th}

number, and so on). That can be simplified further! All

n^{th}

numbers where

n

is an integer and divisible by

3

are even! Let’s verify that!

f(0)=0

which is even,

f(3)=2

(even),

f(6)=8

(even),

f(9)=34

(even) and so on. The beauty here is that it holds for all numbers in the sequence:

f(3n)

is even for every integer

n

greater or equal than

0

.

Our mission was to sum up all even numbers from the Fibonacci sequence, so this now boils down to

f(0)+f(3)+f(6)+… = \sum\limits_{n=0}^{n_{max}} f(3n)

Recurrecurrecurrecurre… (recurrence)

I can elaborate many lines on this, but I try to keep it short. Next step is to convert this problem into another problem for which we know the solution.

We try to find an

x

that satisfies the following requirement:

x^n=f(n)

Does this

x

exists and if so, how does it look like? Let’s try to plug it in into the formula for the Fibonacci sequence:

f(n+2)=f(n+1)+f(n) \Rightarrow x^{n+2} = x^{n+1} + x^n

This can be rewritten as follows:

x^n(x^2 + x + 1)=0

Interesting! Note the polynomial factor. Let’s define

r(x)=x^2+x+1

to simplify the above expression to

x^n r(x) = 0

. After doing some basic math, we can find the solution for

x^2+x+1

, namely

x_1 = \frac{1}{2} + \frac{1}{2} \sqrt{5}

and

x_2 = \frac{1}{2} - \frac{1}{2} \sqrt{5}

. So both

x_1^n

and

x_2^n

are solutions for our problem. In other words, both

f(n)=x_1^n

and

f(n)=x_2^n

hold. But notice the following: we can modify our initial equation as follows:

That mean that if

q^n

is a solution to the problem, then

\alpha q^n

is also a solution to the problem. And also notice the following: suppose that

u^n

and

v^n

are solutions to the problem. Then

u^n + v^n

are also solutions to the problem. In general, if

u^n

and

v^n

are solutions to the problem, then

c u^n + d v^n

are solutions to the problem.

Now we have a little more information! We know that

x_1

and

x_2

are solutions to the problem, so we know that

c x_1^n + d x_2^n

is a solution to the problem for any real numbers

c

and

d

. Since

f(0)=0

we can derive the following:

f(0)=0 \Rightarrow cx_1^0 + dx_2^0 = c + d = 0 \Rightarrow d = -c

Next equation:

f(1)=1

gives the following insight:

f(1)=1 \Rightarrow cx_1 + dx_2 = 1 \Rightarrow c x_1 - cx_2 = 1 \Rightarrow c = \frac{1}{x_1 - x_2}

Et voila!

c = \frac{1}{x_1 - x_2}

and

d = -c = -\frac{1}{x_1 - x_2}

This also solves the overall formula:

f(n) = c x_1^n + d x_2^n = \frac{x_1^n - x_2^n}{x_1 - x_2} = \frac{(\frac{1}{2} + \frac{1}{2} \sqrt{5})^n - (\frac{1}{2} - \frac{1}{2} \sqrt{5})^n}{\sqrt{5}}

What a monster! Let’s try out for

f(2)

for which we know that

f(2)=f(1)+f(0)=1+0=1

:

f(2) =\frac{(\frac{1}{2} + \frac{1}{2} \sqrt{5})^2 - (\frac{1}{2} - \frac{1}{2} \sqrt{5})^2}{\sqrt{5}} = \frac{\frac{1}{4} + \frac{5}{4} + \frac{1}{2}\sqrt{5} - \frac{1}{4} + \frac{1}{2}\sqrt{5} - \frac{5}{4}}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}} = 1

What a beauty!

Back to the summing

So, we were asked to sum all even numbers in the Fibonacci sequence up to some number. Okay, I have to admit that this is the only point where I use a computer. It is asked to consider only the terms in the Fibonacci sequence that do not exceed 4 million. A quick check on the computer gives me that

which is slightly less than 4 million and

f(34)=5702887

. So

n=33

is the

n

such that its element in the Fibonacci sequence is the largest which does not exceed 4 million. Since it is a multiple of

3

, it even simplifies our problem. We want to sum up all even numbers of the Fibonacci sequence and remember that these are the elements

f(3n)

for any integer

n

. So we seek

f(0) + f(3) + f(6) + … + f(33)

. In other words, we seek

\sum\limits_{n=0}^{11} f(3n)

. By our beautiful equivalent of

f(n)

found earlier, we know that this equals:

\sum\limits_{n=0}^{11} f(3n) =\sum\limits_{n=0}^{11} f(3n) =\sum\limits_{n=0}^{11} \frac{x_1^{3n} - x_2^{3n}}{x_1 - x_2}

Don’t be scared! We can simplify this down further:

\sum\limits_{n=0}^{11} f(3n) =\sum\limits_{n=0}^{11} \frac{x_1^{3n} - x_2^{3n}}{x_1 - x_2}=\frac{1}{x_1 - x_2} \sum\limits_{n=0}^{11} x_1^{3n} - x_2^{3n}

We can also split the sum:

\frac{1}{x_1 - x_2} ( \sum\limits_{n=0}^{11} x_1^{3n} - x_2^{3n}) =\frac{1}{x_1 - x_2}\sum\limits_{n=0}^{11} x_1^{3n} -\frac{1}{x_1 - x_2} \sum\limits_{n=0}^{11} x_2^{3n}

And now we only need to know how we can calculate these sums easily.

Solve

\sum\limits_{n=0}^m a^{kn}

So, we first start with a definition. Let

a

be a real number (warning: I actually have very strict about

a

, but I will do it less strict here). Let

k

be a real number and let

m

be an integer larger or equal than 0. Define:

s = \sum\limits_{n=0}^m a^{kn}

Then:

a^k \cdot s = a^k \cdot \sum\limits_{n=0}^m a^{kn} = \sum\limits_{n=0}^m a^{k{n+1}} = \sum\limits_{n=1}^{m+1} a^{kn}

And now subtract the two to cancel out a lot of common terms:

a^k \cdot s - s = s(a^k - 1) = a^{k{m + 1}} - 1 \Rightarrow s = \frac{a^{k{m+1}}-1}{a^k - 1}

Cool! Problem solved.

Putting all the parts together

We need to compute

\sum\limits_{n=0}^{11} x_1^{3n} -\sum\limits_{n=0}^{11} x_2^{3n}

and we know have the tool to do so!

Now we can fill in the found numbers for

x_1

and

x_2

:

And with a calculator (actually by using Scala) we now can find the answer to the original question:

4613732

Conclusion (TL;DR)

4613732

, and do not use math here. It gives beautiful results and generalize results, but a simple functional programming approach (by brute forcing all numbers) would have been way faster to solve this problem:

/**
  * Calculate the nth Fibonacci number.
  *
  * @param n index in the sequence
  * @return nth Fibonacci number
  */
def fibonacci(n: Int): Int = {
    if (n == 0) return 0
    if (n == 1) return 1
    fibonacci(n - 1) + fibonacci(n - 2)
}

/**
  * Calculate the sum of even Fibonacci numbers which do not exceed m.
  *
  * @param m upper bound
  * @param k current index to try out
  * @return sum of even Fibonacci numbers up to m
  */
def sum(m: Int, k: Int): Int = {
    // Calculate the kth Fibonacci number
    val f = fibonacci(k)
    // If f does not exceed m and f is even, then give back f plus the sum of the remaining sequence
    if (f < m && f % 2 == 0) return f + sum(m, k + 1)
    // If f exceeds m, then there is no interesting result to be found
    if (f >= m) return 0
    // Otherwise, f is not even, so only sum over the remainder of the sequence
    sum(m, k + 1)
}

println(sum(4000000, 0))

Subscribe for regular AI & Data Science updates.

Enter your email
Subscribe