Today we are going to start talking about Fibonacci numbers and algorithms to compute them. In particular, we are just going to introduce the sequence of Fibonacci numbers. And talk a little bit about their properties. So, to begin with the Fibonacci numbers is a fairly classically studied sequence of natural numbers.
The zeroth element of the sequence is zero. The first element is one. And from there on each element is the sum of the previous two. So, zero and one is one. One plus one is two. One plus two is three. Two plus three is five. And then the sequence continues eight, 13, 21, 34 and so on. So, it is a nice sequence of numbers defined by some pretty simple recursive rule. And it is interesting for a number of reasons.
It has some interesting number theoretic properties. But originally this sequence was developed by an Italian mathematician, as a mathematical model. And it is a little bit weird. You might try and wonder what sorts of things this could be a model for. Well, it turns out that originally this was used as a sort of a mathematical model for rabbit populations. There was some idea that if you had a pair of rabbits it would take them one generation to mature and every generation thereafter, they would produce a pair of offspring.
And if you work out what this means. Then you find out that the Fibonacci numbers tell you how many pairs of rabbits you have after n generations. Now because rabbits are known for reproducing rather quickly you might assume that this sequence, therefore, grows quickly. And in fact, it does.
It is not hard to show that the nth Fibonacci number’s at least two to the n over two. For all n at least six. And the proof can be made by induction. You prove this directly for n six or seven just by computing the numbers and showing that they are big enough. And after that point. F of n is the sum of Fn minus one and Fn minus two. By the inductive hypothesis you bound that below and do a little bit of arithmetic. And it is bounded below by two to the n over two. So that completes the proof.
In fact, with a little bit more work you can actually read a formula for the nth Fibonacci number. As roughly one-point square root of five over two to the n. These things grow exponentially quickly. And to sort of drive that home a little bit more.
We can look at some examples:
The 20th Fibonacci number is 6,765.
The 50th Fibonacci number is approximately 12 billion.
The 100th Fibonacci number is much, much bigger than that.
And the 500th Fibonacci number is this monster with something like a hundred digits to it.
So, these numbers do get rather large. Quite quickly. So, the problem is how do you compute Fibonacci numbers? So, if you want to use them to model rabbit populations, or because of some number theoretic interest.
We would like an algorithm that as input takes a non-negative integer n. And returns the nth Fibonacci number!