# Connectedness of tree height, b-adic numbers and repunits

The cool thing about math is that abstraction allows us to see similar patterns where we wouldn't expect them to be. A quite trivial but in the same way amazing thing connects number systems, trees, combinatorics and repunits.

## Complete Trees

A complete search tree with branching factor $$b$$ has 1 node at the root, $$b$$ nodes beneath the root node and since every node will have $$b$$ child nodes again until it's a leaf, the number of elements at height $$k$$ is $$b^k$$. If we want to find the total number of nodes in the tree we get to

$s_n = \sum\limits_{k=0}^n b^k$

## Binary unit system

If we have a complete binary search tree, what we actually do is summing over the positions of a number in base two, where all digits are one, meaning that for all $$a_i=1$$ in

$s_n = \sum\limits_{k=0}^n a_i\cdot 2^k$

For a general base $$b$$ we can sum over all the positions in the number and arrive at

$\begin{array}{rrl}& s_n =\sum\limits_{k=0}^n b^k &= 1+b+b^2+...+b^n\\\Leftrightarrow & b\cdot\sum\limits_{k=0}^n b^k &= b+b^2+b^3+...+b^{n+1}\\\Leftrightarrow & \sum\limits_{k=0}^n b^k - b\cdot\sum\limits_{k=0}^n b^k &= (1+b+b^2+...+b^n)- (b+b^2+b^3+...+b^{n+1})\\\Leftrightarrow & (1-b)\cdot\sum\limits_{k=0}^n b^k &= 1-b^{n+1}\\\Leftrightarrow & \sum\limits_{k=0}^n b^k &= \frac{1-b^{n+1}}{1-b}\\\end{array}$

which is the famous partial geometric series, which was already known by Euclid. Now the interesting thing. For a problem I needed to construct a $$n$$ digit number of all 1. Intuitively this can be done by calculating $$10^n$$, subtracting one to get n nines and divide by 9, or more formally $$\frac{10^n-1}{9}$$. This can be expressed differently as $$\sum\limits_{i=0}^{n-1}10^k$$ and is called repunit, since it repeats the unit of a base $$n$$ times.

To make a long story short - the conclusion from all that is, that a partial geometric series with base $$b$$ and a completely filled tree with branching factor $$b$$ are all just repunits, which means that they all are just a number with all 1 in base $$b$$.

You might also be interested in the following