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
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, 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 =  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
\[ 1 + 1 + 1 = 1 + 2 \]
two possibilities in total.