# Counting tree nodes that end probabilistically

Suppose we have $$N$$ root nodes that can branch into $$N$$ new nodes every level. There is a maximum of 64 levels. However, on any given step, each node has a chance $$P$$ of terminating. What is the expected value of $$S$$, the total number of nodes in the tree?

$$S = \sum\limits_{n=0}^{63}(1-P)^n *N^n$$
Each level should be expected to contain $$C[N(1-P)]$$ nodes, where $$C$$ is the number of nodes on the previous level. This is because every $$C$$ that survives, which is $$C(1-P)$$ on average, multiplies to $$N$$ more nodes. Thus the expected total, $$S$$ is indeed
$$S = N\sum\limits_{n=0}^{63} \left[N(1-P)\right]^n$$