A Finite Rule and Exponential Growth

A small rule makes a large structure

Follow this tree outward. Each branch ends in two smaller branches, and each of those branches follows the same rule. A short instruction has produced this entire arrangement. The shape becomes more elaborate without requiring a longer instruction for every new fork.

Now another generation appears. The earlier branches remain, while every outer tip receives two children. We have changed the number of repetitions, not the rule. Look across the new outer branches: the additions occur throughout the tree, rather than only at one growing tip.

Come closer to one junction. Its parent and two children display the local rule that produced the larger structure. The children are shorter, but the count is still two. A scale change concerns length; branching concerns how many descendants each parent supplies.

Pull back to the whole tree. We will connect this local fork to two different questions: how many branches belong to the newest generation, and how many belong to the complete construction? Those questions sound similar, but their answers are different.

Count generations without losing the root

Begin with the trunk and its first pair of children. The trunk is generation zero. Its two children form generation one. There are two branches in that newest generation and three branches altogether. We keep the original trunk when its children appear.

Repeat the rule once more. Each of the two children now has two children of its own. Two groups of two give four branches in generation two. The complete tree contains the trunk, the first pair, and these four newcomers: seven branches altogether.

Look closely at the left-hand parent and its two children. This small group contributes only part of the newest generation. Its partner on the other side has another pair. Counting one visible fork and calling it the whole generation would miss that second contribution.

Visit the corresponding junction on the right. Again, one parent supplies two children. Both junctions obey the same instruction. This is why multiplying the number of parents by two counts the new generation: we collect equal-sized groups without counting any child twice.

Return to the complete construction and locate both pairs. The two groups of children occupy different parts of the picture, but their counts combine. The trunk and the previous generation remain visible below them. Keep those older branches separate from the newcomers while counting.

Why the newest generation doubles

Add generation three. The four branches of generation two each supply two children, giving eight new branches. The full count is one plus two plus four plus eight, which equals fifteen. Notice that eight and fifteen describe the same picture in different ways.

Move outward to a junction in this larger tree. Even here, the local instruction has not become more complicated: one parent, two children. The increasing complexity comes from applying that instruction to more parents simultaneously, not from changing what a parent does.

Pull back before extending the construction. A generation count refers to a complete level, including branches on both sides. When the tree becomes crowded, following the rule is more reliable than trying to count every short line separately in a small image.

Add generation four. Eight parents now supply sixteen children. Altogether there are thirty-one branches: one, two, four, eight, and sixteen across the five generations beginning at zero. The level index is four, while the number of included levels is five.

The newest counts were two, four, eight, and sixteen. Repeated multiplication by two is called exponential growth. Two to the fourth power means four factors of two multiplied together. It counts generation four here; it does not count every branch in the tree.

Change the branching rule

Return to one repetition, and give each parent three children instead of two. The trunk now supports a fan of three. That is three branches in generation one and four altogether. The rule changed, so the counting pattern must change with it.

Repeat the three-child rule. Each of the three parents produces three children, giving nine in generation two. Add the older levels and the full tree contains one plus three plus nine, or thirteen branches. Three squared counts the newest level only.

Approach the left junction and find its three children. Their directions differ, but direction does not determine the number of children. This junction accounts for three of the nine new branches. The other two first-generation parents supply two more equal groups.

Return to the overview. The central child can line up with its parent, so a straight-looking path may contain more than one branch segment. A branch is one step in the recursive construction, from its starting junction to its endpoint. It is not necessarily an isolated line in the picture.

Repeat once more. Nine parents produce twenty-seven new branches, and the complete count becomes forty. Compare this with the binary tree at the same depth: its newest generation had eight and its total was fifteen. The number of repetitions alone cannot determine the count.

Compare different rules at the same depth

Now use four children per parent and return to two repetitions. Watch the four-way fans form. We keep the depth fixed while changing the branching rule, so the difference comes from how many children each parent creates rather than how many times we repeat.

The complete levels are one, four, and sixteen. Their sum is twenty-one. Generation two contains four times four branches, while the whole tree also includes the root and its four immediate children. Twenty-one is therefore larger than the newest count sixteen.

Examine a single four-child junction. Four equal groups of this kind contribute the sixteen newcomers in generation two. The fan shape helps separate them visually; the mathematical count comes from the parent-child relationships. Changing their angles would not change those relationships.

Return to the whole construction. Binary, ternary, and quaternary branching at depth two produced totals seven, thirteen, and twenty-one. Their newest generations were four, nine, and sixteen. Those comparisons use exactly the same convention about the original root.

For contrast, let each parent produce just one child. At depth four we get a single bent chain with five segments. Each new generation contains one branch. The total increases by one per repetition; there is no growing collection of parents to multiply.

Connect the newest level to the whole

Return to the binary tree at depth three. Read its levels from the trunk outward: one, two, four, eight. Adding them gives fifteen. The newest level is larger than all the earlier levels combined by exactly one branch. Here, eight is one more than seven.

At depth four, the newest level has sixteen branches, while the older levels total fifteen. Together they give thirty-one. This explains the binary pattern: the total through a level is twice that level’s count, minus one. We are counting branches, not measuring their lengths.

Compare ternary branching at depth two. The newest level has nine branches, and the total is thirteen. Doubling nine and subtracting one would give seventeen, which is wrong here. The convenient binary shortcut depends on two children per parent and must not be reused for every rule.

Look back at the binary case. You can always count the complete finite tree by adding its generation counts, even without a shortcut. For a branching factor called b, those counts are one, b, b squared, and so on through the chosen depth. The addition collects every included generation.

Use the rule before reading the result

Keep this binary tree at depth two for a prediction. If we add one more generation, how many new branches should appear? First count the parents in the current outer level. Then apply the two-child rule to every one of them. Keep the old branches in a separate total.

Now reveal the next generation. Four parents produced eight children, and the previous seven branches remained. Seven plus eight gives fifteen altogether. The new generation count and the new total answer separate questions, and both follow from the same local construction.

Choose Interact if you want to test another prediction. Set three branches and depth two, predict the newest and complete counts, then increase depth to three. Use the branch count and depth controls deliberately; changing the angle is a different experiment. Resume restores the lesson’s position.

The large picture comes from a small rule applied repeatedly. Every junction supplies the same number of children, generations record successive applications, and the total collects all those generations including the root. In the next lesson, we will follow individual branches and identify exactly how each one arrived here.