Fibonacci sequence

The Fibonacci sequence is defined recursively to be

f(1) = 1
f(2) = 1
f(n) = f(n – 1) + f(n – 2) for n > 2.

The sequence originated with a problem in a text by the Italian mathematician Fibonacci, who introduced to western Europe the algebra and numerals of the Arabian world in about the year 1200. The problem, translated from his words, is:

How many pairs of rabbits can be bred in one year from one pair? A certain person places one pair of rabbits in a certain place surrounded on all sides by a wall. We want to know how many pairs can be bred from that pair in one year, assuming it is their nature that each month they give birth to another pair, and in the second month after birth, each new pair can also breed.
His analysis was that after the second month, the number of new rabbits is the sum of the number bred two months earlier and the number bred the previous month. The sequence begins, then, with the numbers

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

Numbers in the Fibonacci sequence, called Fibonacci numbers, arise in a wide variety of applications.