Fibonacci Sequence¶

Here's a very famous sequence of numbers, known as the Fibonacci sequence:

We start with $1, 1$ and then we add together the last two numbers to get the next one: $1+1=2$, $1+2=3$, $2+3=5$, $3+5=8$ and so on.

Here's a simple Python function that calculates the $n$'th Fibonacci number, e.g. fib(1) == 1, fib(2) == 1, fib(3) == 2 and so on:

def fib(n):
    if n <= 2:      # fib(1) == 1, fib(2) == 1
        return 1
    return fib(n-1) + fib(n-2)

The last line calculates two previous Fibonacci numbers and adds them together. The code works just fine, but something like fib(40) really takes a while. That's one reason why the Fibonacci sequence is not only a well-known thing among mathematicians, but also programmers.

Mathematically we could define the Fibonacci sequence $F_n$ like this:

But we can actually create a formula like $F_n = \text{blablabla}$ for any $n=1,2,3,...$ without using $F_{n-1}$ or $F_{n-2}$ in the formula. A fib function implemented with that formula will be way faster than the fib function above.

Golden Ratio¶

Let's start with a simpler problem. We'll try to find any sequence $a_n$ where $n = 1,2,3,...$ so that $a_n + a_{n+1} = a_{n+2}$. A simple sequence would be $a_n = 0$ because $0 + 0 = 0$, but that's not really interesting so we need to try something else.

Turns out that finding sequences like $a_n = x^n$ for some number $x$ works nicely.

This is true if $x=0$, so we have already found 1 solution. Let's find other solutions by dividing both sides by $x^n$. We can do that because $x \ne 0$, so we also have $x^n \ne 0$.

Next we need to use this formula taken from the summary page:

Let's plug in $a=1$, $b=-1$ and $c=-1$.

Here $\pm$ means $+$ or $-$, and I'm using it just to prevent annoying repetition. We need the absolute value bars because we applied a square root on both sides and we ended up with a $\sqrt{x^2} = |x|$ situation on the left side (see the basics page). So now we have three solutions: $x=0$, $x=\frac{1+\sqrt 5}{2}$ and $x=\frac{1-\sqrt 5}{2}$.

The positive solution $\frac{1 + \sqrt 5}{2}$ is known as the golden ratio, and it occurs in many other places as well. It's usually denoted with the greek phi letter:

Let's calculate approximate values of our solutions with Python:

>>> import math
>>> (1 + math.sqrt(5))/2
1.618033988749895
>>> (1 - math.sqrt(5))/2
-0.6180339887498949

Note how the same sequence of digits repeats. Let's find out what's going on:

The Formula¶

If we have a sequence $a_n$ so that $a_n + a_{n+1} = a_{n+2}$, then we can multiply both sides of the equation by any constant $A$ and we get $A\ a_n + A\ a_{n+1} = A\ a_{n+2}$. So maybe the formula of the famous $1,1,2,3,5,8,...$ sequence is of the form $A \varphi^n$? Let's try that.

I can already tell that this isn't going to work. $F_1 = 1$ means that $A \varphi^1 = A \varphi = 1$ and $A = \frac 1 \varphi$, but $F_2 = 1$ means that we also have $A \varphi^2 = 1$ and $A = \frac{1}{\varphi^2}$. It seems that $\varphi=\varphi^2$, and that's not correct.

That didn't work, but that's just one of the solutions of our equation. Let's make an educated guess with all solutions and three constants $A$, $B$ and $C$:

As before, we also have the initial values $F_1 = 1$ and $F_2 = 1$.

This isn't difficult to calculate by hand, but it's quite tedious, so we'll use sympy:

>>> from sympy import *
>>> init_printing()
>>> A,B,phi = symbols('A B phi')
>>> A,B,phi
(A, B, φ)
>>> def fib(n):
...     return A*phi**n + B*(1-phi)**n
... 
>>> solve([Eq(fib(1), 1), Eq(fib(2), 1)], A,B)
⎧      1          -1   ⎫
⎨A: ───────, B: ───────⎬
⎩   2⋅φ - 1     2⋅φ - 1⎭

Note that I didn't plug in the actual value of $\varphi$; instead I'm using a symbol called $\varphi$ so I can get the result in terms of $\varphi$.

We can't wait to try this out! Let's do it.

>>> values = solve([Eq(fib(1), 1), Eq(fib(2), 1)], A,B)
>>> values[phi] = (1 + sqrt(5))/2
>>> values
⎧      1          -1        1   √5⎫
⎨A: ───────, B: ───────, φ: ─ + ──⎬
⎩   2⋅φ - 1     2⋅φ - 1     2   2 ⎭
>>> fib(1).subs(values).simplify()
1
>>> fib(2).subs(values).simplify()
1
>>> fib(3).subs(values).simplify()
2
>>> fib(4).subs(values).simplify()
3
>>> fib(5).subs(values).simplify()
5
>>> fib(6).subs(values).simplify()
8
>>> fib(7).subs(values).simplify()
13

It works! I think this is really amazing.

Let's simplify the A and B values:

>>> values[A].subs(phi, values[phi]).simplify()
√5
──
5 
>>> values[B].subs(phi, values[phi]).simplify()
-√5 
────
 5  

These can be also written as $\frac{1}{\sqrt 5}$ and $-\frac{1}{\sqrt 5}$ because $5 = (\sqrt 5\ )^2$, but sympy likes to put square roots to top for some reason. Anyway, with this we can write a much cleaner formula:

There it is! If you like code obfuscation, you can replace the constants with hard-coded floats:

>>> from math import sqrt
>>> (1 + sqrt(5))/2
1.618033988749895
>>> (1 - sqrt(5))/2
-0.6180339887498949
>>> sqrt(5)
2.23606797749979
>>> def lelfib(n): return (1.618033988749895**n - (-0.6180339887498949)**n)/2.23606797749979
... 
>>> lelfib(1)
1.0
>>> lelfib(2)
1.0
>>> lelfib(3)
2.0
>>> lelfib(4)
3.0000000000000004
>>> lelfib(5)
5.000000000000001
>>> lelfib(6)
8.000000000000002
>>> lelfib(7)
13.000000000000002
>>> lelfib(8)
21.000000000000004

The formula is correct as we'll see in a moment. Floats are not meant to be mathematically precise, so the little precision problems are not a surprise.

The Proof¶

Now we have a nice formula, but we haven't actually proved that it works yet. We just plugged in some values and we got nice results. It's time to prove that this sequence...

...satisfies our original definition of the Fibonacci sequence:

This will be a proof, so we won't use sympy.

The $F_1=1$ thing is quite straight-forward to prove:

We need the handy thing at right for $F_2=1$.

We already figured out that this is 1 when proving that $F_1=1$.

If we can prove that $F_n + F_{n+1} = F_{n+2}$ for $n=1,2,3,...$, then we also have $F_n = F_{n-1} + F_{n-2}$ for $n=3,4,5,...$ which is what we need next. In the beginning of this page we solved $x^n+x^{n+1}=x^{n+2}$ and we got the solutions $x=\varphi$, $x=1-\varphi$ and $x=0$, so we have these equations:

Now we're ready to go. I'll color everything $F_n$ related in blue and everything $F_{n+1}$ related in green so you can see what happens to them.