A tree, a geometric sum, and a numeral made entirely of ones seem to belong to different parts of mathematics. Yet all three are descriptions of the same object. The connection becomes especially clear when a perfect tree is built one level at a time.
Counting a Perfect b-ary Tree
In a perfect \(b\)-ary tree, every internal node has exactly \(b\) children and every leaf lies at the same depth. If the root is at level zero, then level \(k\) contains
\[b^k\text{ nodes}.\tag{1}\]
A tree of height \(h\) therefore has
\[N_h=1+b+b^2+\cdots+b^h= \sum_{k=0}^{h}b^k.\tag{2}\]
The following binary example has height three. Its four levels contain 1, 2, 4, and 8 nodes, for a total of 15.
The Same Sum as a Base-b Numeral
A numeral in base \(b\) with digits \(a_ha_{h-1}\ldots a_1a_0\) represents
\[ \left(a_ha_{h-1}\ldots a_1a_0\right)_b =\sum_{k=0}^{h}a_kb^k. \]
Setting every digit to one turns this into exactly the tree count:
\[ \left(\underbrace{11\ldots 1}_{h+1\text{ digits}}\right)_b =\sum_{k=0}^{h}b^k =N_h. \tag{3} \]
A number consisting only of unit digits is called a repunit. More precisely, the base-\(b\) repunit with \(n\) digits is
\[ R_n^{(b)}=\left(\underbrace{11\ldots1}_{n\text{ digits}}\right)_b =\sum_{k=0}^{n-1}b^k =\frac{b^n-1}{b-1}, \qquad b\geq2. \tag{4} \]
The closed form is the finite geometric-series identity. Multiplying the sum by \(b\) shifts every term one position; subtraction cancels the interior terms and leaves only \(b^n-1\).
The index shift matters: a tree of height \(h\) has levels \(0\) through \(h\), hence \(h+1\) levels. Its node count is therefore \(R_{h+1}^{(b)}\), not \(R_h^{(b)}\).
The Stronger Connection: The Same Recursion
The shared sum is already suggestive, but the recursive construction shows that the agreement is structural rather than accidental. Start with one root, \(N_0=1\). To add another complete level, replace every existing position by \(b\) copies and add one new root:
\[ N_h=bN_{h-1}+1. \tag{5} \]
Now consider appending a digit \(1\) to a base-\(b\) numeral. Shifting the existing digits one place to the left multiplies the value by \(b\); writing the final digit adds one:
\[ \left(x1\right)_b=b\left(x\right)_b+1. \tag{6} \]
Equations (5) and (6) are identical. Growing the tree by one level and appending one unit digit are the same recurrence with the same starting value. This explains the connection more directly than the closed formula does.
Examples Across Bases
| Branching factor | Tree height | Level sizes | Total nodes | Base-b form |
|---|---|---|---|---|
| 2 | 3 | 1, 2, 4, 8 | 15 | 1111₂ |
| 3 | 2 | 1, 3, 9 | 13 | 111₃ |
| 10 | 2 | 1, 10, 100 | 111 | 111₁₀ |
The decimal example looks unusual as a tree because every internal node has ten children, but mathematically nothing changes. The familiar decimal repunit 111 is simply the number of nodes in a perfect 10-ary tree of height two.
Constructing Repunits
The recurrence also gives a direct implementation that mirrors the tree construction. Using BigInt keeps the result exact even after ordinary JavaScript integers become unsafe:
function repunit(base, digits) {
base = BigInt(base);
let value = 0n;
for (let i = 0; i < digits; i++) {
value = base * value + 1n;
}
return value;
} For example, repunit(3, 4) returns \(40\), because \(1111_3=1+3+9+27=40\). The loop does not merely compute the same result as the formula: each iteration literally appends one base-\(b\) unit digit, just as each recursive step grows the corresponding perfect tree by one level.