Republic of Mathematics blog

How fast do the Fibonacci numbers grow?

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

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:

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.

Leave a Reply