Fibonacci Numbers

The Fibonacci numbers are a sequence defined as follows:

	
F0 = 0
F1 = 1
Fn+2 = Fn+1 + Fn
	
      

This gives 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .... If φ is the golden ratio, (1+√5)/2, then Fn = round(φn/√5) where round is a function that rounds its argument to the nearest integer. This means that Fibonacci numbers grow exponentially.

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.