Expected Time for LookUpSkipList
The recurrence can be solved as:
$$
\begin{align}
C(k) &amp;= \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}\\
2 \cdot C(k) &amp;= 1 + C(k) + 1 + C(k-1)\\
C(k) &amp;= 1 + 1 + C(k-1)\\
C(k) &amp;= 2 + C(k-1)\\
\end{align}
$$
Then this can clearly be expanded to a summation:
$$
\begin{align}
C(k) &amp;= 2 + C(k-1)\\
&amp;= 2 + 2 + C(k - 2)\\
&amp;= 2 + 2 + 2 + C(k - 3)\\
&amp; \dots\\
&amp;= 2 + 2 + \dots + C(1)\\
&amp;= 2k\\
\end{align}
$$

I haven't done much investigation into skip lists, but the math you've shown checks out. ✓

EDIT

The reason $C(k)$ appears in the left and right side of the equation, which seems concerning, is because of the Skip List structure. Take this procedure (source) to $find(86)$:



Now let's consider the reverse of this path. Notice we always move up if we can. So for any node in the reverse path, we can either (1) move up or (2) move left:


We move up. Now we have $C(k-1)$ more levels up to go: $$1 + C(k - 1)$$
We move left. We have made no progress upwards, therefore we still have $C(k)$ more levels up to go: $$1 + C(k)$$


For a randomized skip list, either of these scenarios occurs with probability $\frac{1}{2}$. This is how we get the final recurrence:

$$C(k) = \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}$$