# Fibonacci Numbers

## Fibonacci Numbers

1,1,2,3,5,8,13,21,34,55,89: what's next?

If you guessed 144, you may be on to something we call the Fibonacci numbers, after Fibonacci, a mathematician who lived about 1200 A.D..

The Fibonacci numbers are generally defined this way: given the two latest Fibonacci numbers, create the next (and newest) Fibonacci by adding them together. So 1+1=2, 1+2=3, 2+3=5, etc. We explain this all mathematically via the recursive algorithm that follows:

F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2), $n\ge 3$


These numbers appear all over in nature: in pinecones, pineapples, artichokes, pussywillows, daisys, etc.

But they started out as pairs of immortal bunnies, which mature in a month, and then produce a single new pair every month thereafter (that's the way Fibonacci began studying them, it seems). We start out on the left, in the diagram which follows, and watch a single baby bunny pair mature, and then begin to populate the world with bunnies:

This diagram illustrates why the recursive algorithm works:

• we assume that the number of bunny pairs arising from a single immature pair is given by the sequence $\left.F(n)\right.$, with generations 1, 2, 3, 4, 5 shown here (although this will continue on forever, of course). At the bottom, in yellow, is the running total of bunny pairs.
• We notice that at the third generation, the total population of pairs is given by the sum of two new populations: a perfect copy of the original tree, starting from the first generation (when there were $\left.F(1)\right.$ bunny pairs), and a perfect copy of the original tree starting from the second generation (when there were $\left.F(2)\right.$ bunny pairs).
• Hence $\left.F(3)=F(2)+F(1)\right.$, $\left.F(4)=F(3)+F(2)\right.$, and so on. So, more generally,
$\left.F(n)=F(n-1)+F(n-2)\right.$

## Fibonacci number decomposition

We "decompose" natural numbers using Fibonacci numbers and sums:

every natural number is either

1. Fibonacci, or
2. can be written as a sum of non-consecutive Fibonacci's in a unique way.

Examples?

Can we justify this?

• If a number is Fibonacci, then we're done.
• Assume a number is not Fibonacci:
• then there is a largest Fibonacci that "fits inside it" -- e.g. 24 = 21 + 3.
• If the remainder (3, in the example above), after subtraction, is Fibonacci, how do we know that it is not consecutive (that is, that it is not 13)? That is, how do we know that the two Fibonacci numbers are not successive Fibonacci numbers?
Because if they were, they could be combined to form a larger Fibonacci number! And we chose the largest Fibonacci possible to start.
• If it is not Fibonacci, can we not simply repeat the current process of looking for a sum for a non-Fibonacci number, but using the remainder instead of the original number? (i.e. can we not simply "recurse" -- that is, do it again, and so construct a chain of numbers leading down towards 1.

Example: 33=21+12=21+8+4=21+8+3+1