Basic Math Concepts made Complicated Quickly

2017-10-15 math

Fibonacci - What’s in a Name…

The man, the myth

Leonardo Fibonacci was a mathematician who lived in the middle ages and was held in high esteem for his prowess as a talented mathematician. Best known for his Fibonacci Sequence which seemingly is simple to define, yet it’s limit point (of the ratio of the last two elements of the sequence) (also known as the Greek letter Phi). The mysticism around the Golden ratio abounds due to its correlation with many natural element - both living things as well as dynamic processes.

The Sequence is easy as one, one, two, … (okay, not one, two, three!)

So, you may already know that the sequence is defined using a recursive relationship. We define the first fibonacci number in the sequence, $F_1 = 1$, and the second fibonacci number in the sequence, $F_2 = 1$. From there, we can generate the subsequent numbers in the sequence using the recursive formula:

$$ F_n = F_{n-1} + F_{n-2} $$

And we can define $ \Phi $ as the limit of the ratio of the two last terms in the sequence.

$$\Phi = \lim\limits_{x \to \infty} \frac{F_{n-1}}{F_{n-2}}$$

So, the question becomes, how do we evaluate the limit and compute the value for $\Phi$? A quick numerical investigation reveals an approximation for $\Phi$.

def fib(n):
  if n > 2:
      return fib(n-1) + fib(n-2)
  elif n == 2:
      return 1
  elif n == 1:
      return 1

def phi(n):
    if n > 2:
        return fib(n-1)/fib(n-2)
    else:
        return 1

If we were to call phi(25) for example, we could approximate $\Phi$ to 1.618033988205325. Not a bad approximation, but what if we wanted to compute an algebraic answer for $\Phi$? Here’s where thinking like a mathematician comes in.

We need to reason about what $\Phi$ actually is, and then we can construct an equation that we can solve for $\Phi$.

Let’s see if we can reason our way through a solution. We know that $\Phi$ is the ratio, but how can we describe the terms of the last two elements of the sequence? It seems counter-intuitive to “find” the last two elements of the infinite sequence. But, we can “describe” them without knowing what the infinitely last two elements are (which would be impossible to do).

Suppose we know that the first element in the sequence is length 1. And let’s use $x$ for the length of the second element.

We can use these two pieces to construct an equation. It turns out that we can make three terms from this information:

$F_1 = 1$
$F_2 = x$
$F_3 = x + 1$

From this we can create two ratios and we know that they must be equal, as they are both $\Phi$ .

$$\frac{F_3}{F_2} = \Phi = \frac{F_2}{F_1}$$

Or, said another way,

$$\frac{x}{1} = \frac{x+1}{x}$$

This is a simple quadratic equation - which we can solve for $x$ using the quadratic formula.

$$x^2-x-1=0$$

$$x = \frac{1 + \sqrt{5}}{2}$$ $$and$$ $$x = \frac{1 - \sqrt{5}}{2}$$

But since we are looking for lengths, we select the positive one. And that’s how you algebraically calculate $\Phi$.

Before we leave the topic, let’s go back to our python code and look at our fibonacci function. We defined this function recursively, meaning that the time required to compute large values of $n$ grows as $n$ grows large. Wouldn’t it be nice to compute the $nth$ value of the sequence in $O(1)$ time? Before we do that, let’s show an implementation of our fib function that is better, but still not $O(1)$.

Instead of recursion, we use iteration.

def fib(m):
        p=1
        n=1
        if m < 2:
                return 1
        else:
            for i in range(m-2):
                    old_n = n
                    n = n + p
                    p = old_n
            return n

Using our calculated value of $\Phi$, we can derive (left as an exercise for the reader) a closed-formula for the $nth$ number in the sequence using the following formula:

$$F(n) = \frac{\Phi^n-(-\Phi^{-n})}{\sqrt{5}}$$

We can rewrite our python code accordingly:

import math

PHI = (1.0 + math.sqrt(5))/2.0

def fib(n):
    return int((math.pow(PHI,n) - math.pow(-1*PHI, -n))/math.sqrt(5))

Using this implementation to numerically compute $\Phi$ is far more efficent. Calling our phi(n) function for 1000 is instantaneous. Try calculating $\Phi$ using the recursive function with the same value of $n$. Be prepared to wait around… for a long… long… time!