(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.

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".