Please take a look at the following image which is a skip list
There are $n$ nodes between the path from $p$ to $x1$, for each node, there is $1/2$ probability to be selected for the next level. suppose from $p$ to $x1$ only $x1$ is selected. It has been claimed that the expected number of elements on the $p ... x1$ path is bounded by a constant.
The expectation relation is as follow:
$1 \times 1/2 + 2 \times (1/2)^2 + 3 \times(1/2)^3 + ... n \times (1/2)^n$
But I can't prove that the above relation is bounded by a constant.
This sum has a nice closed form: $$\sum_{i=1}^n i2^{-i} =2 - n2^{-n} - 2^{-n+1} = 2 - \frac{n+2}{2^n} \leq 2$$ We see it's always less than 2.
There's a cancellation trick to evaluate it, just like evaluating the geometric series. Let $S_n = \sum_{i=1}^n i2^{-i}$. $$S_n = 2S_{n} - S_n = \sum_{i=1}^n i2^{-i+1} - \sum_{i=1}^ni2^{-i}$$ $$ = \sum_{i=0}^{n-1} (i+1)2^{-i} - \sum_{i=1}^{n}i2^{-i} $$ $$= 1 + \left(\sum_{i=1}^{n-1} (i+1)2^{-i} - \sum_{i=1}^{n-1}i2^{-i}\right) - n2^{-n}$$ $$ = 1 + \sum_{i=1}^{n-1}2^{-i}- n2^{-n}$$ $$ = 1 + (1 - 2^{-n+1}) - n2^{-n} = 2 - 2^{-n+1} - n2^{-n}$$