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

The sequence of Fibonacci numbers begins .

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

.

We can write this defining property as a recurrence relation by naming the Fibonacci number , starting from .

So, .

The recurrence for the is then:

x

for with ………………………..(1)

x

When we calculate a few of them we notice a curious thing about the ratio :

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 seems to pretty quickly converge to a number that is approximatelyÂ 1.618033989.

What this means is that, before too long, .

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

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 so let’s divide the recurrence relation (1) by to get:

x

…………………………………………(2)

x

In terms of the name for the ratio , (2) says:

x

………………………………………..(3)

x

If – and for now it is just an “if” – conveges to some number then the difference between becomes very small as increases, so must satisfy:

x

x

………………………………………………(4)

x

x

Multiplying this through by gives a quadratic equation for :

x

…………………………………………….(5)

x

The roots of this quadratic equation are:

x

.

x

This looks promising! It seems the mysterious 1.618033989 is just

In other words, it’s looking like for large .

We have shown that IF converges to a number then that number must be . The ratio cannot converge to the other root of the quadratic because the Fibonacci numbers increase with .

What we have not yet shown is that, in fact, .

How can we do that?

One way is to examine the error and try to show that the error converges to 0 as increases.

All we know about come from (3) and (4).

So:

That is, taking the size of the error:

x

x

Because the Fibonacci numbers increase we know that , so:

x

…………..(6)

x

Because , (6) tells us that the error .

In other words, the ratio as the numerical evidence strongly suggested.

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.

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.

1 | The Science Pundit

December 1, 2010 at 11:19 am

Ah yes: The Golden Ratio!