## Fibonacci Number & Golden Ratio

Posted: March 22, 2017 in Mathematics

Today I saw this funny picture of Donald Trump and then I know why everybody says Golden Ratio can be found all over nature. Yes it is living among us. You can’t escape from it, not even from the president of America.

So, what is Golden Ratio?

In Euclid’s Elements, Book VI Definition 2, Euclid wrote (in Greek of course):

Ακρον καὶ μέσον λόγον εὐθεῖα τετμῆσθαι λέγεται, ὅταν ᾖ ὡς ἡ ὅλη πρὸς τὸ μεῖζον τμῆμα, οὕτως τὸ μεῖζον πρὸς τὸ ἔλαττὸν

Or in English,

A straight-line is said to have been cut in extreme and mean ratio when as the whole is to the greater segment so the greater (segment is) to the lesser.

Or in plain English, it basically says that when you divide a line segment into two uneven pieces, the ratio of the whole line segment to the longer piece equals the ratio of the longer piece to the shorter piece. And this ratio is called the Golden Ratio (often denote as $\phi$).

$\displaystyle\frac{a+b}{a} = \frac{a}{b} = \phi \quad\Leftrightarrow\quad 1+\frac{1}{\phi}=\phi \quad\Leftrightarrow\quad \phi^2=\phi+1$

After solving the quadratic equation, you will get:

$\displaystyle\phi = \frac{1+\sqrt5}{2} \approx 1.61803398874989\ldots$

Now, let’s consider the Fibonacci sequence.

$F_n = 1,1,2,3,5,8,13,21,34,55,89,\ldots$

and examine some nth power of the golden ratio.

$\phi^1 = \phi$

$\phi^2 = \phi+1$

$\phi^3 = \phi^2+\phi = 2\phi + 1$

$\phi^4 = 2\phi^2+\phi = 2(\phi+1) + \phi = 3\phi+2$

$\phi^5 = 3\phi^2+2\phi = 3(\phi+1) + 2\phi = 5\phi + 3$

$\phi^6 = 5\phi^2+3\phi = 5(\phi + 1) + 3\phi = 8\phi + 5$

This suggests that

$x^2=x+1 \quad \Rightarrow \quad x^n = F_n x + F_{n-1} \quad\forall n\in\mathbb{Z}^+$

Let’s define $F_0 = 0$, then

$x^1 = F_1 x + F_0 = x$

$x^2 = F_2 x + F_1 = x+1$

Assume $x^k = F_k x + F_{k-1}$, then

$x^{k+1} = x^k\cdot x = F_k x^2 + F_{k-1} x \\= F_k(x+1)+F_{k-1}x = (F_k+F_{k-1})x+F_k \\ = F_{k+1} x + F_k$

Hence, by math induction, $x^n = F_n x + F_{n-1} \quad \forall n\in\mathbb{Z}^+ \text{ where } x^2=x+1$.

Now, go back to the equation $x^2 = x+1$, the two roots are

$\displaystyle\phi = \frac{1+\sqrt5}{2} \quad\text{and}\quad \Phi=\frac{1-\sqrt5}{2}$

Hence,

$\phi^n = F_n\phi + F_{n-1} \qquad \text{(1)}$

$\Phi^n = F_n\Phi + F_{n-1} \qquad \text{(2)}$

(1) – (2) yields

$\displaystyle F_n = \frac{\phi^n - \Phi^n}{\phi - \Phi} = \frac{\phi^n - \Phi^n} {\sqrt5}$

Or

$\displaystyle F_n = \frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)$

###### Remarks

Since

$\displaystyle\Phi = 1-\phi \quad\text{and}\quad \phi = 1+\frac{1}{\phi}$

then

$\displaystyle F_n = \frac{\phi^n - (1-\phi)^n}{\sqrt5} = \frac{\phi^n-(-\frac{1}{\phi})^n}{\sqrt5}$

$\displaystyle\lim_{n\to\infty}\frac{F_{n+1}}{F_n} = \lim_{n\to\infty} \frac{\phi^{n+1}-(-\frac{1}{\phi})^{n+1}}{\sqrt5} \cdot \frac{\sqrt5}{\phi^n-(-\frac{1}{\phi})^n}$

As $\displaystyle n\to\infty, \quad -\frac{1}{\phi^{n+1}} \text{ and } -\frac{1}{\phi^n} \to 0$

$\displaystyle \therefore \lim_{n\to\infty} \frac{F_{n+1}}{F_n} = \phi$

As $n\to\infty, \quad \displaystyle -\frac{1}{\phi^n} \to 0$

$\displaystyle \therefore F_n \approx \frac{\phi^n}{\sqrt5}$ as n is large.

The last approximation comes in handy when you want to find the nth Fibonacci number, let’s say the 30th Fibonacci number.

$\displaystyle F_{30} \approx \frac{\phi^{30}}{\sqrt5} \approx 832040.00000024\ldots$

So, you can compute the 30th Fibonacci number to be 832040 in seconds with any normal scientific calculator.