In the world of mathematics, the importance of sequences and series in analysis is well established. Sometimes, it’s hard to find a concrete application for concepts invented (or discovered?) in the field. The Fibonacci sequence, on the other hand, can be found in many areas of nature, and continues to fascinate researchers thanks to its properties closely linked to the golden ratio.
History and background
The Fibonacci sequence takes its name from the 13th-century Italian mathematician Leonardo of Pisa, also known as Fibonacci. Although he didn’t invent the sequence, he introduced it to Europe with his book “Liber Abaci” (Book of the Abacus or Book of Calculation) in 1202.
In this book, Fibonacci posed and solved a problem involving the growth of an idealized rabbit population, which leads to this sequence of numbers. It’s worth noting that the Fibonacci sequence was known long before this date in India, where the relationships between the numbers in the sequence were already being studied.
Fibonacci numbers have many applications in nature and art. They can be observed on a variety of scales, from flower petals to galaxy spirals. Flower petals often have Fibonacci numbers – daisies can have 34, 55 or even 89 petals. And sunflower seeds or pine cones are often arranged in spirals following Fibonacci numbers.
In architecture, the golden ratio, directly linked to the Fibonacci sequence, has been used to create works that are pleasing to the eye thanks to their “perfect” proportions. For example, the Parthenon in Greece and the Taj Mahal in India both seem to use the golden ratio in their construction.
It’s this universality that makes the Fibonacci sequence so fascinating – a simple sequence of numbers that finds its way through mathematics, nature and art, uniting fields that might seem remote at first glance. In the next section, we’ll take a closer look at what these numbers are and how we can generate them ourselves using the Python programming language.
Romanesco cabbage hides a secret – count the number of spirals, if you can!
Definition and implementation
Formally, the Fibonacci sequence is a sequence in which each term is equal to the sum of the two preceding elements. Just knowing the first two terms and the recurrence formula is enough to construct the sequence in its entirety.
$F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+ F_{n-2}$ for $n \geq 2$.
Building a program to provide the nth Fibonacci number is a very good elementary exercise. Before reading on, you can try coding the function yourself!
Here’s a Python function to solve the problem:
def fibonacci(n):
if n in {0, 1}:
return n
return fibonacci(n-1) + fibonacci(n-2)
This initial recursive implementation may be satisfactory, but there is scope for optimizing this code by opting for an iterative approach. Recursion is very restrictive in terms of computation time; in fact, the time complexity of this function is O(n²). In practice, this means that the function struggles to deliver a result within a satisfactory timeframe when n is large (for example, n = 40).
Here’s a new approach, this time iterative, which produces the same result using a for loop:
def fibonacci(n):
a, b, c= 0, 1, 0
if n == 0:
return 0
for i in range(2, n+1):
c = a + b
a = b
b = c
return b
One way of optimizing this code would be to cache the elements of the sequence as they are introduced, so as to avoid redundant calculations each time the function is called.
In addition, there’s a mathematical formula for calculating the exact term of the sequence without recursion. Called Binet’s formula, it uses the golden ratio :
def fibonacci(n):
sqrt5 = math.sqrt(5)
F_n = int((( (1 + sqrt5) ** n - (1 - sqrt5) ** n ) / ( 2 ** n * sqrt5 )))
return F_n
Conclusion
The Fibonacci sequence is used in a wide variety of fields, such as cryptography and trading. Among other things, it can be used to generate a list of pseudo-random numbers or to create an elementary encryption system.
In finance, a tool called the Fibonacci retracement level is used to estimate how far an asset could fall before resuming its trend movement. In time series analysis, Fibonacci numbers are used to determine the optimum number of time periods to use in calculating moving averages.
