Fibonacci for beginners

The Fibonacci sequence is one of the most famous sequences. It appears everywhere in nature and mathematics. It is defined as:

\[ F(1) = 1 \] \[ F(2) = 1 \] \[ F(n) = F(n – 1) + F(n – 2) \]

We don’t want to calculate all these numbers by hand. For n = 100 the number has more than twenty digits. Addition is easy for humans and even easier for computers. Let’s write it with some Python, because everybody loves Python:

def fib(n):
    if n < 3:
        return 1
    return fib(n - 1) + fib(n - 2)

The code mirrors the above definition nicely. For numbers smaller than 1 it returns 1, which may be undesirable. We could return None, but that is a whole different discussion.

When executing this code for n = 100 it takes a while, a long while, and my computer starts to lag. It can’t handle the recursion depth. For n = 40 it takes more than 20 seconds to compute the value 102334155. How do we fix this? With a loop:

def fibiter(n):
    if n < 3:
        return 1
    a = 0
    b = 1
    for _ in range(n):
        a, b = b, a + b
    return a

The iterative approach starts to take longer at n = 100 ^ 2. Scaling much better than the recursive aproach.

Related to the Fibonacci sequence is the Pascal triangle. The sum of every diagonal is equal to the next number in the Fibonacci sequence, but don’t take my word for it. Here is some code to make a Pascal triangle and see for yourself:

def pascal(N):
    """Create list of N pascal triangle rows"""
    triangle = []
    row = [1]
    for n in range(N):
        triangle.append(row[:])
        for i in range(1, len(row)):
            row[i] += triangle[n][i - 1]
        row.append(1)
    return triangle


def diag_sum(p):
    """Diagonal sums of a pascal triangle"""
    sums = []
    for d in range(len(p)):
        s = 0
        for i in range((d + 2) // 2):
            s += p[d - i][i]
        sums.append(s)
    return sums

It is quite phenomenal how often the Fibonacci sequence pops up its head. In nature one can find the sequence too. Flowers have a pattern that follows the expansion of this sequence and rabits reproduce at the rate of the Fibonacci sequence.

Now for a little puzzle that you can easily google, if you want to. Given that you can use only 1s and 2s to sum a number, how many possibilities are there for a number n? For example if n = 3 we get:

\[ 1 + 1 + 1 = 1 + 2 \]

two possibilities in total.

Leave a comment

Your e-mail address will not be published. Required fields are marked *