# Fibonacci Sequence¶

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

$$\begin{align}1, 1, 2, 3, 5, 8, 13, 21, ...\end{align}$$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:

$$\begin{align}\left\{\begin{array}{lcl} F_1 = 1 \\ F_2 = 1 \\ F_n = F_{n-1} + F_{n-2}, \quad n = 3,4,5,... \\ \end{array}\right.\end{align}$$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.

$$\begin{align}x^n + x^{n+1} &= x^{n+2}\end{align}$$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$.

$$\begin{align}\frac{x^n}{x^n} + \frac{x^{n+1}}{x^n} &= \frac{x^{n+2}}{x^n} \\ 1 + x &= x^2 \\ 0 &= x^2 - x - 1\end{align}$$Next we need to use this formula taken from the summary page:

$$\begin{align}ax^2+bx+c = a\left(x + \frac{b}{2a}\right)^2 + c - \frac{b^2}{4a}\end{align}$$Let's plug in $a=1$, $b=-1$ and $c=-1$.

$$\begin{align}x^2-x-1 &= 0 \\ 1\left(x + \frac{-1}{2\cdot1}\right)^2 + (-1) - \frac{(-1)^2}{4\cdot1} &= 0 \\ \left(x - \frac 1 2\right)^2 - 1 - \frac 1 4 &= 0 \\ \left(x - \frac 1 2\right)^2 &= 1 + \frac 1 4 = \frac 4 4 + \frac 1 4 = \frac 5 4 \\ \sqrt{\left(x - \frac 1 2\right)^2} &= \sqrt{\frac 5 4} \\ \left|x - \frac 1 2\right| &= \frac{\sqrt 5}{\sqrt 4} = \frac{\sqrt 5}{2} \\ x - \frac 1 2 &= \pm \frac{\sqrt 5}{2} \\ x &= \frac 1 2 \pm \frac{\sqrt 5}{2} = \frac{1 \pm \sqrt 5}{2}\end{align}$$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:

$$\begin{align}\varphi = \frac{1+\sqrt 5}{2}\end{align}$$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:

$$\begin{align}\frac{1-\sqrt 5}{2} &= \frac{2-1-\sqrt 5}{2} = \frac{2-(1+\sqrt 5)}{2} \\ &= \frac 2 2 - \frac{1+\sqrt 5}{2} = 1 - \varphi\end{align}$$## 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.

$$\begin{align}\left\{\begin{array}{lcl} F_n = A \varphi^n \\ F_1 = 1 \\ F_2 = 1 \\ F_n = F_{n-1} + F_{n-2} \\ \end{array}\right.\end{align}$$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$:

$$\begin{align}F_n &= A \varphi^n + B (1-\varphi)^n + C \cdot 0 \\ F_n &= A \varphi^n + B (1-\varphi)^n\end{align}$$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:

$$\begin{align}F_n &= A \varphi^n + B (1-\varphi)^n \\ &= \frac{1}{\sqrt 5} \varphi^n - \frac{1}{\sqrt 5} (1-\varphi)^n \\ &= \frac{\varphi^n - (1-\varphi)^n}{\sqrt 5} \\ &= \frac{\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 - \sqrt 5}{2}\right)^n}{\sqrt 5}\end{align}$$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...

$$\begin{align}F_n = \frac{\varphi^n - (1-\varphi)^n}{\sqrt 5}, \quad n = 1,2,3,...\end{align}$$...satisfies our original definition of the Fibonacci sequence:

$$\begin{align}\left\{\begin{array}{lcl} F_1 = 1 \\ F_2 = 1 \\ F_n = F_{n-1} + F_{n-2}, \quad n = 3,4,5,... \\ \end{array}\right.\end{align}$$## Handy thing: $(a-b)^2=a^2-2ab+b^2$

Proof using $(a-b)c=ac-bc$:

$$\begin{align}& \ (a-b)^2 \\ =&\ (a-b)(a-b) \\ =&\ a(a-b)-b(a-b) \\ =&\ (aa-ab)-(ba-bb) \\ =&\ aa-ba-ab+bb \\ =&\ aa-(ab+ab)+bb \\ =&\ a^2-2ab+b^2\end{align}$$In this case we need to plug in $a=1$ and $b=\varphi$.

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

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

$$\begin{align}F_1 &= \frac{\varphi^1 - (1-\varphi)^1}{\sqrt 5} = \frac{\varphi - (1-\varphi)}{\sqrt 5} \\ &= \frac{\varphi-1+\varphi}{\sqrt 5} = \frac{2\varphi - 1}{\sqrt 5} = \frac{\rcancel 2 \frac{1+\sqrt 5}{\rcancel 2} - 1}{\sqrt 5} \\ &= \frac{\rcancel{1}+\sqrt5\rcancel{-1}}{\sqrt5} = \frac{\sqrt5}{\sqrt5} = 1\end{align}$$We need the handy thing at right for $F_2=1$.

$$\begin{align}F_2 &= \frac{\varphi^2 - (1-\varphi)^2}{\sqrt 5} \\ &= \frac{\varphi^2-(1^2-2\cdot1\cdot\varphi+\varphi^2)}{\sqrt 5} \\ &= \frac{\rcancel{\varphi^2}-1+2\varphi\rcancel{-\varphi^2}}{\sqrt5} = \frac{2\varphi-1}{\sqrt5}\end{align}$$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:

$$\begin{align}& \varphi^n + \varphi^{n+1} = \varphi^{n+2} \\ & (1-\varphi)^n + (1-\varphi)^{n+1} = (1-\varphi)^{n+2}\end{align}$$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.

$$\begin{align}\blue{F_n} + \green{F_{n+1}} &= \blue{\frac{\varphi^n - (1-\varphi)^n}{\sqrt 5}} + \green{\frac{\varphi^{n+1} - (1-\varphi)^{n+1}}{\sqrt 5}} \\ &= \frac{\blue{\varphi^n-(1-\varphi)^n}+\green{\varphi^{n+1}-(1-\varphi)^{n+1}}}{\sqrt 5} \\ &= \frac{\blue{\varphi^n}+\green{\varphi^{n+1}}-\blue{(1-\varphi)^n}-\green{(1-\varphi)^{n+1}}}{\sqrt 5} \\ &= \frac{\left(\blue{\varphi^n}+\green{\varphi^{n+1}}\right)-\left(\blue{(1-\varphi)^n}+\green{(1-\varphi)^{n+1}}\right)}{\sqrt 5} \\ &= \frac{\varphi^{n+2} - (1-\varphi)^{n+2}}{\sqrt 5} = F_{n+2}\end{align}$$