# Number of nodes in Van-Emde-Boas tree of universe size u?

The universe size $$u$$ in vEB trees is square rooted at each level until $$u = 2$$. So, unlike search trees, the branching factor is different at each level.

The height of the tree is $$h = \lg \lg(u)$$ and $$u$$ is an even power of 2, $$u = 2^{2^k}$$. I tried to calculate the count using the sum:

$$\sum_{i=1}^{h-1} 2^i\,2^{i + 1}$$

But it doesn’t work. Any idea on how to do the math?