How to understand the probablistic analysis of skiplist? I've been studying the skiplist analysis from the open data structures book here:
Open Data Structures
I've understood the first 3 lemma's, (after looking at how they use indicator variables in the section 1.3.4 of the book).
However, Lemma 4.4 seems pretty vague. Especially, how is
$$\sum_{r=1}^{\lfloor\log n\rfloor}1 + \sum_{r=\lfloor\log n\rfloor+1}^\infty n/2^r\leq\log n + \sum_{r=0}^\infty 1/2^r\,?$$
The first sum is obviously equal to $\lfloor\log n\rfloor\leq\log n$.

For the second sum, assuming that logs are base-$2$ and using $r&gt;\lfloor\log n\rfloor$,

$$2^r = 2^{\lfloor\log n\rfloor+1}2^{r-\lfloor\log n\rfloor-1} \geq n2^{r-\lfloor\log n\rfloor-1}\,,$$

and the result follows.  If the logs aren't base-$2$, then there'll be a scaling factor but the second sum will still be $\Theta(1)$.