This question already has an answer here:
I know the space requirements for a van Emde Boas tree is $Θ(u)$, and that the recurrence relation for this looks like:
$$S(u) = (\sqrt u + 1) S(\sqrt u) + Θ(\sqrt u)$$
I'm curious and can't seem to find it anywhere but, how would one go about proving this recurrence relation is true? I.e., how do you prove $S(u) = Θ(u)$ ?