# Why divide by $b-1$ when computing size of a tree

In one of the lectures I went to, my professor stated that in order to determine the size of a search tree, we use the following formula: $$\frac{b^{d+1}-1}{b-1},$$ whee $b$ is the branching factor and $d$ is the depth of the tree in question. I would like to understand why we divide by $b-1$. I would have thought that the correct solution is $b^{d+1}-1$.

• You're probably tricked by usually nice case of $b=2$, where you have $2-1 = 1$.
– user5386
Dec 14 '16 at 20:25

There are $b^i$ nodes at depth $i$, and so the total number of nodes is $$1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1},$$ using the formula for the sum of a geometric progression.