TAOCP 6.2.1 Exercise 16

Section 6.2.1: Searching an Ordered Table

Exercise 16. [21] [21] Figure 9 shows the lineal chart of the rabbits in Fibonacci’s original rabbit problem (see Section 1.2.8). Is there a simple relationship between this and the Fibonacci tree discussed in the text?

Initial pair

First month Second month

Third month VA\
Fourth month

[| Fifth month [ l \ L\ \

Sixth month l \ \

Fig. 9. Pairs of rabbits breeding by Fibonacci’s rule.

Verified: no
Solve time: 1m58s

Let the Fibonacci rabbit model be the standard one: a single initial pair is present at month $0$; every pair produces exactly one new pair in each month starting from its second month of life; no pair dies. Let $f_k$ be the number of pairs at month $k$. Then

$$ f_k = f_{k-1} + f_{k-2}. $$

1. Precise structure of the lineal chart

Interpret the lineal chart as a directed graph:

Each vertex represents a rabbit pair.
There is a directed edge from a pair $x$ to a pair $y$ if and only if $x$ is the unique parent that produced $y$.
The initial pair is the unique root (it has no parent).
Each vertex has exactly one parent except the root, because every newborn pair is created by exactly one existing pair.

Hence the graph is a rooted tree. The “time layers” in the lineal chart are just a drawing convention: vertices are placed according to birth month.

2. Fibonacci tree in TAOCP form

The Fibonacci tree $T_k$ is defined recursively as follows:

$T_0$ is a single node.
$T_1$ is a single node.
For $k \ge 2$, the root of $T_k$ has two ordered subtrees:
a left subtree $T_{k-1}$,
a right subtree $T_{k-2}$.

No additional relabeling or shifting is involved. The structure is entirely determined by this recursion.

3. Key structural observation

Both constructions encode the same dependency rule:

In the rabbit model, the population at month $k$ consists of:
all pairs already present at month $k-1$,
plus the new pairs born from pairs present at month $k-2$.
In the Fibonacci tree, the tree $T_k$ consists of:
a copy of $T_{k-1}$,
and a copy of $T_{k-2}$, attached as disjoint subtrees of the root.

Thus both objects are built from the same recursive decomposition.

4. Correct bijection between the structures

Define a mapping $\phi$ from rabbit pairs to nodes of Fibonacci trees as follows:

The initial pair corresponds to the root of $T_k$ at the appropriate stage.
If a pair $x$ produces a new pair $y$, then $\phi(y)$ is the child node in the tree corresponding to that reproduction event.

More concretely, define the structure inductively by month:

At month $k$, the set of all rabbit pairs is identified with the nodes of $T_k$.
The root corresponds to the initial pair.
The subset of pairs already present at month $k-1$ corresponds to the $T_{k-1}$ subtree.
The subset of newly born pairs (born at month $k$) corresponds to the $T_{k-2}$ subtree, since a pair born at month $k$ arises from a parent present at month $k-2$.

This yields a bijection between nodes and rabbit pairs that preserves parent-child relations.

5. Consistency of levels

A node’s level in the Fibonacci tree corresponds to its birth month in the rabbit model:

Root: month $0$.
A child created from a node at month $i$ appears at month $i+2$ (because reproduction has a two-month delay).
Hence each level of the tree corresponds exactly to a time layer in the lineal chart.

Thus “level” and “month” are the same grading of the same structure.

6. Conclusion

The lineal chart of Fibonacci’s rabbit problem is exactly an embedding of the Fibonacci tree $T_k$ into the plane with vertices arranged by birth time. The Fibonacci tree is the abstract form of the same genealogy, obtained by forgetting the geometric placement and retaining only the parent-child structure.

Therefore, the relationship is simple:

$$ \text{The lineal chart is a time-layered drawing of the Fibonacci tree, and the Fibonacci tree is the abstract genealogy of the rabbit chart.} $$