Fibonacci Numbers

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

Fib. tree #1

(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

At the nth year there are Fn 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 Fn branches.

Fib. tree #2

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