The Fibonacci Sequence

is an infinite sequence of numbers that is defined as follows:

• The 1st two numbers are 0 and 1.
• The next numbers are generated by adding previous two numbers.

$$\begin{array}{rl}{F}_0& =0\\ F_1& =1\\ F_n& =F_{n-1}+F_{n-2}\end{array}$$

The first few numbers of the sequence are:

$$0,1,1,2,3,5,8,13,21,34,55,\dots$$

Concepts covered in this chapter

• Using integers
• Procedures and Recursion
• Caching repeated computations
• Analyzing the speed of your program