The Fibonacci Sequence: An Algorithm for Perfection

Original article was published on Artificial Intelligence on Medium

Mathematics

The Fibonacci Sequence: An Algorithm for Perfection

Fibonacci Series Explained Easily

Fibonacci was a 13th-century Italian mathematician who gave birth to one of the most notorious algorithms in mathematics.

In this article, I will explain its history, its mathematical importance, and finally, the code that I will run to replicate it.

Count the Rabbits

Initially, Fibonacci created this mathematical model to win a competition run by Frederick II, a real authentic genius of the time. The math problem was the following:

“There is a couple of rabbits in an enclosed space. Given that every month one couple is going to generate another couple that can become productive after one month, how many couples of rabbits can we count after 1 year?”

Photo by Kedar Gadge on Unsplash

Fibonacci solved the problem in this way and then published it in his book Liber Abaci, 1202.

Complete list of Active, Inactive, Total rabbit couple for every month of the year

Step I

As you can see, the process is simple: to discover the number of rabbit couples in the second month, we begin by copying the Active number of couples of the first month in the Inactive spot of the second month: what it means is that each of the couples in Month 0 (1) has produced another couple that will remain Inactive for Month 1 (1).

Step II

To discover how many Active couples there will be in Month 0, we just need to add the couples that are already active (1) with the couples that will become active the following months (The Inactive couples at Month 0).

Result

At last, we have easily found out the number of rabbit couples in the month to come.

We can keep iterating this process month after month like Fibonacci did until we reach Month 12.

Summary of the Sequence

The entire sequence, in plain numbers, is the following:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377…

The Recursion problem

What is so particular about this sequence? First of all, it is an algorithm, NOT a function. What this means is that we cannot just jump at any given number of the Fibonacci sequence.

If I only gave you a piece of paper and a pen and I asked you to calculate me the 1000th number of the sequence, there is no way you could jump to it directly, and you would need to undergo the process above until you reach the 1000th number:

26,863,810,024,485,359,386,146,727,202,142,923,967,616,609,318,986,952,340,123,175,997,617,981,700,247,881,689,338,369,654,483,356,564,191,827,856,161,443,356,312,976,673,642,210,350,324,634,850,410,377,680,367,334,151,172,899,169,723,197,082,763,985,615,764,450,078,474,174,626

***This is not a sequence, is a real number

Therefore, recursion holds many problems in terms of computation. Another example of recursion are prime numbers: there is no prime number formula because the sequence of prime numbers is recursive. You cannot generate the nth prime number, and you need to check if it has any dividers apart from 1 and itself. The bigger the number, the bigger the computational load.

Fibonacci sequence in the real world

The Fibonacci sequence has incredible applications in the real world, especially for pattern predictions.

We can use each number of the sequence to build a sequence of Squares:

Retrieved from: www.blogpositivo.it

0, 1, 1, 2, 3, 5, 8, 13…

As you can see in the center of the image, the first square has a side of length 1. The second square will still have a side of length 1. If we add them together, we obtain a square with the side of length 2 that can cover the sum of the sides of the two squares placed one upon the other. With the rectangle, we just build we can create a square with the side of length 3, and so on.

If we connect the same vertex of every square we built, we have a spiral.

Retrieved from: newbiescience.wordpress.com

Fibonacci in mathematical terms

However fascinating may the description be, we have to encompass the sequence in the mathematical language:

With the algorithm we just created, we can give the right instructions on how to retrieve any number of the Fibonacci sequence we want.

The Golden Ratio

The Golden ratio represents the perfect proportions. It has been around since the Greeks, who introduced it in the world of art.

Image from www.pinterst.com

While the Greeks were using an alternative formula to find it (Fibonacci would have been born 800 years later), you can use the Fibonacci sequence to figure it out:

Every major masterpiece in art follows this proportion that artists and mathematicians find harmonious.

Code

Last but not least, this is how the Fibonacci sequence looks in code:

def Fibonacci(n):
if n <= 1:
return n
return(Fibonacci(n-1) + Fibonacci(n-2))

If we run the code inputting 7 as the nth number of the Fibonacci sequence:

Fibonacci(7)
13