2 - Fibonacci Numbers and the Start of Modern Mathematics

The Problem:

Link
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.

Background:

When we think of great European mathematicians our minds tend to go to two places, either the the Greeks, like Euclid, Archimedes, or Pythagoras, who basically perfected the math of Geometry.  Or our minds go to the 16th and 17th century mathematicians, Euler, Leibniz, or Newton.  But rarely do we think of people from from the High Middle Ages.  But without the work of Leonardo of Pisa, who you may also know as Fibonacci, we might not have seen the latter European mathematicians.

Fibonacci is probably most known for the famous Fibonacci sequence.  For those unaware this sequence traditionally starts with 0 and 1.  Each next term in the sequence is generated by adding the previous two. So you wind up with the following sequence of numbers \(0, 1, 1, 2, 3, 5, 8, 13, ...\)  The fibonacci sequence shows up a lot in nature and in places in mathematics where you wouldn't expect it.  However, I would argue that this sequence is probably one of his least important contribution to the field.  His biggest contribution was something that he didn't even invent.  In my opinion, Fibonacci's greatest achievement was in popularizing the Arabic numerals, and introducing zero to Europe.

The number 0 is an important number.  Technically its introduction only added one number over the previous system, and numerically it represents nothing.  But zero's impact is more about how number are thought of.  With 0, numbers become playthings.  They are more abstract, ethereal, but they become more like objects. Before zero was introduced numbers represented a count, a description of something.  A number could be a count of sheep in the field, or the acres of land owned by a lord, or the number of regiments in an army, or the salary that each one was paid.  There was no reason to have the number 0, because you didn't have to represent nothing as a number.  No one would have said I have zero sheep grazing in the field.  They would have said there is no number, because none of them were grazing.  Back at this time those who did math, merchants, bankers, and tax collectors, would use roman numerals.  This system, instead of using digits in a specific base, worked more like a tally system.

Num	Numeral	Num	Numeral	Num	Numeral	Num	Numeral
1	I	6	VI	20	XX	500	D
2	II	7	VII	30	XXX	1000	M
3	III	8	VIII	40	XL	2014	MMXIV
4	IV	9	IX	50	L	1776	MDCCLXXVI
5	V	10	X	100	C	1202	MCCII

To be able to do math with Roman numerals with any sort of efficiency a person would need to use an abacus.  Adding was simple enough, it was more difficult to perform multiplication, and very difficult to exponentiate.  That might have been part of the reason why European mathematics didn't advance much before this time.

Allow me to deviate from the math of the times, to something a little more modern.  I recall a story from the autobiography of one of my favorite physicists, Surely You're Joking, Mr. Feynman, by Richard Feynman.  A cursory search on YouTube found this clip from the movie Infinity, though this movie takes artistic liberty with the version in the autobiography, it has the right spirit.  The actual story goes that one day, while in a restaurant Feynman came across a Chinese man trying to sell an abacus.  One thing led to another and Feynman found himself in a contest seeing who could tabulate the fastest him with a pen and paper, the salesman with an abacus.  One challenge was to add a bunch of numbers together, and the abacus won that in a landslide.  The next challenge was multiplication, and this round was much closer, though the man with the abacus won by a hair.  The last challenge was to find the solution to a cube root, and Feynman blew the salesman out of the water. By the time the man with the abacus answered, Feynman was figuring out what the fifth and sixth digits after the decimal were.

This story reflects what was happening in Europe regarding mathematics between 1200 and 1700.  Algorismists and abacists were at odds debating the best way to manipulate numbers, and it really wasn't until Leibniz that the algorismists won definitively.  The mathematics of the Renaissance and Enlightenment demanded a more flexible number system, and by the time calculus came around, math required it.  It was Fibonacci who first introduced algorism to Europe, treating numbers as something other than a count.  It would be a long transition, but Fibonacci can and should be credited with getting the ball rolling on it.

Not too much is known about the life of Leonardo of Pisa.  We can estimate that he was born around 1170 to a wealthy merchant in Pisa.  Because his father was a merchant Leonardo got to travel to various trading ports with him and help his father sell his wares.  One of the places his father traded was a North African trading post, in modern day Algeria.

We should remember the time period Fibonacci is operating in. When we think back to the early 13th century we think of the era that is backwards.  I won't attest to the veracity of this claim, I'm just a simple blogger, but the idea that the time after the fall of the Roman Empire in the 7th century up to the 15th century was a Dark Age has been with us since the Renaissance.  During this time, the Catholic Church dominated the life and politics of the age.  During 1202, when Fibonacci was writing his Liber Abaci, Europe was between the third and fourth crusade.  The infamous Enrico Dandolo was the Doge of Venice. There were knights and serfs, feudalism and manorialism.  The Black Death, which started in the 1340s, was still over a century away.


Algeria at this time was under the rule of a Muslim sultan of the Almohad dynasty.  The native merchants, and those traveling from the middle east used numbers which were very different than what Leonardo would have been accustomed to.  The Almohads used a number system which was given to them by the Arabs, which was introduced to them by the Hindus.  The system is what we now call Arabic numerals, or Hindu-Arabic numerals if you care to be more politically correct.  This is the number system we use today, using the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 to represent any conceivable number in base-10.  I assume you are familiar with it, so I won't explain it further, but if you care to see a documentary about the number system, narrated by Terry Jones, of Monty Python fame, check out this link.  At this point in history the Indians and the Arabs are centuries ahead of Europe mathematically.  They regarded negative numbers as numbers in their own right, not as absurd numbers as Europeans would regard them well into the 16th century.

I can imagine Leonardo walking through the Berber market, young and curious.  All of the merchants know him, he walks around often, and they call him "Fibonacci" meaning son of a simpleton.  He might ask to see the records of sales from one of the merchants, and be introduced to some strange system of math.  He asks what the symbols mean and is drawn to the logic and simplicity of them.  I can also imagine him staying awake by candle light after his father had packed up all his goods onto the trade ship.  He is a child, and he does what kids do, play.  He takes the numbers and adds them together in new patterns, he squares them and multiplies them.  It was at this point that the young Fibonacci might have asked his father permission to travel the Arab world and learn what there is to know about this new and beautiful math.  And he did travel, and he didn't return to Pisa until the turn of the century, in 1200.

In 1202 Fibonacci wrote his famous Liber Abaci.  He then toured Europe, going on one of the first book tours in Europe. He was pitching the Arabic numeral system like a salesman might pitch you a car.  One of the surprising parts of this story is that he was largely successful.  Could you imagine as a merchant at this time some guy who's name means "son of a simpleton" come up to you and says, "you know that way you and everyone else count, it's wrong.  And by the way, the Muslims have a much better system."  I'm not sure to what esteem the merchants held the Muslims, but there were ongoing crusades in Europe at this time.  Which might have been why the number system took so long to introduce.  To the Europeans at the time, this was the enemies of Christendom number system, and Roman numerals had worked just fine for the greatest empire the world had seen up to that point, which was the Roman Empire of course.  But Fibonacci was successful, merchants started using Arabic numbers; the number system stuck.  And his success just goes to show how much better it was for merchants to use Arabic numerals in their accounting.

Eventually the Holy Roman Emperor Frederick II took note of Fibonacci.  And Frederick II wasn't your typical emperor, at least, he wasn't the type of guy who comes to mind as Imperial.  He became King of Sicily when he was 4, King of the Germans by age 18, and was elected Holy Roman Emperor at age 26.  But, instead of spending his time in Germany he stayed in Sicily for most of his life.  He founded the first secular university in Naples, and he collected philosophers and poets like they were Pez dispensers.  He had good relations with the Islamic sultan in the Middle East, yet detested by the Pope. He was practically given the city of Jerusalem by the sultan Al-Kamil.  Possibly becoming the only person in history to peacefully take control of the region.  Yet he was excommunicated, twice by Pope Gregory. 

Fibonacci moves to the court of Emperor Frederick II where he is given a salary, and becomes one of the first state sponsored mathematician.  Fibonacci continued working until his death some time between 1240 and 1250, dedicating one of his last books, Liber quadratorum, aka The Book of Squares to the Emperor Frederick.

So, Fibonacci was one of the first mathematicians in Europe since the classical age.  And we can credit him, if not for the invention, then at least the revival of doing math for math's own sake in Europe, and the mathematical paper.  He did then what we are doing now.  Solving problems unknown to him using the tools that math gave him for no other reason than because he enjoyed it.  Unfortunately Fibonacci is really only remembered for a silly sequence for calculating the population of rabbits over.  This silly sequence could probably be thought up by a four year old just learning how to add, but it still has a few secrets.  And fortunately, there is another problem down the road where I can go very much into detail about the magic behind the sequence. This has the added benefit of sparing you from reading even more, I do tend to ramble on these things.  So in the spirit of Fibonacci, we can finally start the problem.

The Math:

The problem asks us to sum numbers in the Fibonacci sequence, and as it turns out there is a formula to help us find it.  As with the last problem, we could create all of the Fibonacci numbers, check if each is divisible by two, and add it to a rolling sum.  But as is often the case with these problems, there is another way to do it.

n	F(n)	Sum
1	1	1
2	1	2
3	2	4
4	3	7
5	5	12
6	8	20
7	13	33
8	21	54
9	34	88
10	55	143

If the pattern of isn't obvious then I'll just outright say it, the sum of Fibonacci numbers \(F_n\) is \(F_{n+2} -1\).  And there is a neat proof for this fact, but before I start, it might be worth talking about proof by induction.

Induction is a very poweful proof technique.  The premise of inductionis that if you can prove that the statement for n also implies n+1, and you can prove the statement for some number n, usually 1 or 0, then the proof will hold all the way down the line of natural numbers.  Induction has been comparted to dominos, if you can prove that a domino will push the domino in front of it down after it falls, and you can also prove that the first domino has been pushed, you can prove all the dominos will fall down.  It may be easier to figure out induction after seeing it.
First I'm going to define some numbers:
\( F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2\)
We want to prove that:
 $$\forall n \ge 1 : \sum\limits^{n}_{i=0}F_i = F_{n+2} - 1$$
So we prove the base case \(n = 0\)
$$F_0 = F_2 - 1 = 1 - 1 = 0$$
So the basis holds.

Now we prove the induction hypothesis:
$$\sum\limits^{k}_{i=0}F_{i} = F_{k+2} - 1 \implies \sum\limits^{k+1}_{i=0}F_{i} = F_{k+3} - 1$$
$$\begin{align}
\sum\limits^{k+1}_{i=0}F_{i} & = \sum\limits^{k}_{i=0}F_{i} + F_{k+1} \nonumber \\
& = (F_{k+2} - 1) + F_{k+1} \nonumber \\
& = (F_{k+1} + F_{nk+2}) -1 \nonumber \\
& = F_{k+3} - 1\nonumber \\
\end{align}
$$
 So \(P(k) \implies P(k + 1) \)

Therefore:
 $$\forall n \ge 1 : \sum\limits^{n}_{i=0}F_i = F_{n+2} - 1$$

Induction seems a bit like a magic trick to me.  You start out saying you want to prove some statement, you assume that it's true, do a bit of math, and then suddenly it becomes true.  It feels like we are using a word in the definition of that word.

When we look at the sums of the even Fibonacci numbers, there is no immediate patter that arrives, however, let's remember that each successive term in the Fibonacci sequence is equal to the sum of the two preceding terms.  By excluding every odd number we are really just dividing the sum of all the numbers in half.

$$\begin{align}
S & = 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + \ldots \nonumber \\
S & = (1 + 1) + 2 + (3 + 5) + 8 + (13 + 21) + 34 + \ldots \nonumber \\
S & = (2) + 2 + (8) + 8 + (34) + 34 + \ldots \nonumber \\
S & = 2*2 + 2*8 + 2*34 + \ldots \nonumber \\
S/2 & = 2 + 8 + 34 + \ldots \nonumber \\
\end{align}
$$

n	F(3n)	Sum	2*Sum
1	2	2	4
2	8	10	20
3	34	44	88
4	144	188	376

In this table, I use F(3n) to denote the even Fibonacci numbers, which occur at every third index.  If we add 1 to twice the sum we get 5, 21, 89, and 377 which are the Fibonacci numbers of index 5, 8, 11, and 14 respectively.  Those indexes follow an arithmetic sequence, and can be described as \(F_{3n+2}\).  There is a proof for this, but it gets a little hairy, and there isn't much point relaying it here.  The formula for the sum of even Fibonacci numbers is: 

$$\sum\limits_{i = 0}^{n}F_{3i} = \dfrac{F_{3i + 2}-1}{2}$$

Unfortunately, this equation is useless to us.  I fooled you.  We don't know what position the index of the highest Fibonacci number below four million, and even if we did, adding numbers isn't hard for a computer to do, in fact, it's what a computer does best.  The amount of time you save computing the next two terms in the Fibonacci sequence as opposed to keeping a rolling sum, if any, is minimal.  Now, there is a way to calculate the nth Fibonacci number using only the index n, and knowing nothing else.  But that will have to wait for for the next Fibonacci post.

The Code

Python

Okay, even though I just said it was useless, I'm showing you the strategy for finding Fibonacci numbers.  One thing to keep in mind is that we don't know what the highest Fibonacci number under 4 million is.  There are three cases, that the highest Fibonacci number under 4 million is even, the one before that is even, or the one before that is even.

#Find the sum of the even Fibonacci numbers under 4000000
MAX = 4000000 #Highest number possible in the sequence
lastnum = 1
num = 1

while num < MAX:
    num += lastnum
    lastnum = num - lastnum

#num is even
if num & 1 == 0: 
    finalnum = num + (num + lastnum) #The Fibonacci number n+2
    print((finalnum -1)/2)

elif lastnum & 1 == 0:
    finalnum = num + lastnum
    print((finalnum-1)/2)

else:
    finalnum = num
    print((finalnum-1)/2)0

You might have noticed in my code that I'm not using a modulus operator (%) to check if a number is divisible by two, and therefor even.  Instead I'm using an ampersand (&) which is a bitwise and operator.  By 'anding' the number with one I'm effectively ignoring everything but the last digit of the number, which can either be 1 if the number is odd, or zero if the number is even.  This is slightly more efficient to use than a modulus operate, though not by much.  It would mean much more if I was checking evenness within a loop.  Just thought I would share some new notation.

My method for calculating fibonacci numbers might be a little confusing, but "num" changes its value before it is used to change the value of "lastnum."  So "num" becomes the next item in the sequence, and I am undoing that number to get teh original num, then assigning that value to last num.

Running a time benchmark, this code takes pretty much exactly 5 milliseconds to complete.  Not to shabby, but I won't be breaking any records.

C

As with the last problem, I did this problem slightly differently with C.  I'm keeping a running total of each instance where the sum is even.  Except, I'm not checking to see if a number is even, I already know that every third number is even.  I'm not doing the trick with the bitwise and, but the effect is still similar.

#include <stdio.h>

main(){
    int fibo, lastf;
    int summa;
    int i;
    lastf = 1;
    fibo = 2;
    
    i = 0;
    while (fibo < 4000000){
        if (i == 0){
            summa += fibo;
        }
        fibo += lastf;
        lastf = fibo - lastf;
        i = (i+1)%3;
    }
    printf("%d\n", summa);
}   

This program goes way faster, mostly because it is in C, about and doesn't have to deal with an interpreter. About 21 microseconds.  Comparing times from python to c is like comparing the lap time of a sprinter and a marathon runner.  They aren't competing in the same event, so it's pointless.  If you want to make something out of the times, try writing your own problem and see if you can do better.