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.