How fast do the Fibonacci numbers grow?

Posted by: Gary Ernest Davis on: December 1, 2010

In: Uncategorized
Comment!

0 Shares

Fibonacci numbers

Leonardo Fibonacci (c. 1170 â€“ c. 1250)

The sequence of Fibonacci numbers begins $1, 1, 2, 3, 5, 8, 13, 21,\ldots$ .

The defining feature of these numbers is that each is the sum of the preceding two:

$2=1+1, 3=2+1, 5=2+3, 8=5+3, 13=8+5, 21=13+8, \ldots$ .

We can write this defining property as a recurrence relation by naming the $n^{th}$ Fibonacci number $F_n$ , starting from $n=0$ .

So, $F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_6=8, F_7=13, F_9=21,\ldots$ .

The recurrence for the $F_n$ is then:

$F_n=F_{n-1}+F_{n-2}$ for $n\geq 2$ with $F_0=1=F_1$ ………………………..(1)

How rapidly do the Fibonacci numbers grow?

When we calculate a few of them we notice a curious thing about the ratio $\frac{F_n}{F_{n-1}}$ :

$n$	$F_n$	$\frac{F_n}{F_{n-1}}$
0	1
1	1	1
2	2	2
3	3	1.5
4	5	1.666666667
5	8	1.6
6	13	1.625
7	21	1.615384615
8	34	1.619047619
9	55	1.617647059
10	89	1.618181818
11	144	1.617977528
12	233	1.618055556
13	377	1.618025751
14	610	1.618037135
15	987	1.618032787
16	1597	1.618034448
17	2584	1.618033813
18	4181	1.618034056
19	6765	1.618033963
20	10946	1.618033999
21	17711	1.618033985
22	28657	1.61803399
23	46368	1.618033988
24	75025	1.618033989
25	121393	1.618033989
26	196418	1.618033989
27	317811	1.618033989
28	514229	1.618033989
29	832040	1.618033989
30	1346269	1.618033989

The ratio $\frac{F_n}{F_{n-1}}$ seems to pretty quickly converge to a number that is approximatelyÂ 1.618033989.

What this means is that, before too long, $F_n\approx 1.618033989\times F_{n-1}$ .

Because $1.618033989 > 1$ , this means that the Fibonacci numbers appear to increase exponentially, with a multiplication factor of about 1.618033989.

What’s going on?

Can we give a reason why the Fibonacci numbers increase exponentially, other than numerical evidence from a table of values?

And where does that strange number 1.618033989 come from?

Everything we know, and can know, about the Fibonacci numbers comes from the recurrence relation (1).

We are interested in the ratio $R_n:=\frac{F_n}{F_{n-1}}$ so let’s divide the recurrence relation (1) by $F_{n-1}$ to get:

$\frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}}$ …………………………………………(2)

In terms of the name $R_n$ for the ratio $\frac{F_n}{F_{n-1}}$ , (2) says:

$R_n=1+\frac{1}{R_{n-1}}$ ………………………………………..(3)

If – and for now it is just an “if” – $R_n$ conveges to some number $\phi \textrm{ as } n\to \infty$ then the difference between $R_n \textrm{ and } \phi$ becomes very small as $n$ increases, so $\phi$ must satisfy:

$\phi=1+\frac{1}{\phi}$ ………………………………………………(4)

Multiplying this through by $\phi$ gives a quadratic equation for $\phi$ :

$\phi ^2-\phi -1 =0$ …………………………………………….(5)

The roots of this quadratic equation are:

$\frac{1}{2}(1+\sqrt{5}) \approx 1.618033989\textrm{ and } \frac{1}{2}(-1+\sqrt{5}) \approx 0.618033989$ .

This looks promising! It seems the mysterious 1.618033989 is just $\frac{1}{2}(1+\sqrt{5})$

In other words, it’s looking like $F_n \approx \frac{1}{2}(1+\sqrt{5}) \times F_{n-1}$ for large $n$ .

Can we prove it?

We have shown that IF $R_n=\frac{F_n}{F_{n-1}}$ converges to a number then that number must be $\phi = \frac{1}{2}(1+\sqrt{5})$ . The ratio cannot converge to the other root of the quadratic because the Fibonacci numbers increase with $n$ .

What we have not yet shown is that, in fact, $R_n \to \phi \textrm{ as } n\to \infty$ .

How can we do that?

One way is to examine the error $E_n:=R_n-\phi$ and try to show that the error converges to 0 as $n$ increases.

All we know about $R_n\textrm{ and } \phi$ come from (3) and (4).

So:

$E_n=R_n-\phi=(1+\frac{1}{R_{n-1}})-(1+\frac{1}{\phi}) =\frac{1}{R_{n-1}}-\frac{1}{\phi}= \frac{\phi-R_{n-1}}{\phi\times R_{n-1}} = -\frac{E_{n-1}}{\phi\times R_{n-1}}$