Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most
Hint: Show that at a given value of $i$, the probability of failure of the $l$th attempt is at most $i/m \leq 1/2$ (perhaps using a union bound), and the events are independent for different attempts.