There are $n$ elements in a hash table of size $m \geq 2n$ which uses open addressing to avoid collisions.
The hash function was chosen randomly among a set of uniform functions. A set $H$ of hash-functions $h:U\to\{0,\dots,m-1\}$ is called uniform, if for every tuple of different keys $x,y \in U$ the number of hash-functions $h \in H$ with $h(x) = h(y)$ is $\frac{|H|}{m}$ at most.
Show that the propability that for $i = 1, 2, \dots,n$ the $i$-th insert operation needs more than $k$ attempts, is $2^{-k}$ at most.
This is an assignment, which I got as homework. What I already worked out:
The propability $p_1$ for a collision is 0 of course for an empty table.
The propability $p_i$ for a collision after k attempts should be $\frac{i - 1}{2n}\cdot k$ assuming that the table is filled with $i-1$ elements to this point and the tables size is $2n$ as worst case.
So I have $$ p_i= \frac{i-1}{2n} \cdot k \leq 2^{-k}, $$
but I don't know where to go from here.
The method of open hashing used here simply iterates over different hash-functions until a free place is found (for example $h(x) = (x \bmod j) \bmod n$ with increasing prime numbers for $j$.
