Formula for Nodes in a Tree

74 Views Asked by At

I am reading section 1.5.2 in this book where they claim that for a tree with branch factor $b$, the number of nodes at distance $R$ from the root is given by

$$N(R)=(b+1)b^{R-1}$$

However, I just don't see this. Let us imagine the following graph:

enter image description here

The branching factor is $b=4$. When R=0 we are at the root node and there is one node. There are 4 nodes in the first layer (a distance of $R=1$) and 16 in the second layer (a distance of $R=2$). I would therefore say that $N(0)=1, N(1)=4, N(2)=16$ and hypothesise that

$$N(R)=b^R$$

Where am I going wrong?