algorithms - Determining the space complexity of van Emde Boas trees

We call S(u) the space complexity of the vEB tree holding elements in the range 0 to u-1, and suppose without loss of generality that u is of the form 2^2k.

It's easy to get the recurrence S(u²) = (1+u) S(u) + Θ(u). (In Wikipedia's article the last term is O(1), but it's wrong because we must count the space for the array.)

Van Emde Boas gave in [1] the trivial bound S(u) = O(u log log u), and later in [2] he found a clever way to combine the data structure with other one so that to reach space complexity O(u), while mantaining the O(log log u) time bounds.

But modern references present the original data structure and state without proof that the space complexity is O(u). For instance, the very recent 3rd edition of "Introduction to algorithms" by Cormen et al. leaves it as an exercise.

I tried with some friends to [dis]prove the O(u) bound without luck.

[1] http://www.springerlink.com/content/h63507n460256241/

[2] http://www.cs.ust.hk/mjg_lib/Library/VAN77.PDF