## Fibonacci Numbers

The Fibonacci numbers (A000045) are illustrated
by the following diagram:

(Figure drawn by Henry Bottomley, July 27 2000.)

If turned sideways (so that the red node at the left is at the bottom), this may be regarded as the
**Fibonacci Tree**,
which grows according to the rules that

- every red node turns blue after a year

- every blue node produces one blue node and one red node after a year

- initially there is a single red node

At the nth year there are F_{n} nodes.

Here is a different representation of the same tree.

This grows according to the rules that
every mature branch sprouts a new branch
at the end of each year, and new branches take
a year to reach maturity.

Mature branches are indicated by heavy lines.

At the end of the nth year there are F_{n} branches.

Another version of the Fibonacci tree can be constructed as follows.
Start with a node labeled 0.

From any given node, draw branches extending
up from it labeled n+1 and 2n.

In this way every node is labeled with a unique nonnegative integer,
and every nonnegative integer appears exactly once.

This is the "state diagram" for the process "if n is even divide by 2,
if n is odd subtract 1".