# algorithms – Prove that if \$k\$ was the \$(i+1)\$st key to be inserted into the hash table, then \$E[probes(k)]=frac{1}{1-frac{i}{m}}\$

Theorem: Inserting an element into an open-address hash table with load factor α requires at
most $$1/(1 − α)$$ probes on average, assuming uniform hashing.

By following unsuccessful search strategy, we find out that average number of probes is $$E(probesge i) = frac{1}{1-alpha}$$ where $$alpha = frac{n}{m}$$, $$n$$ is elements and $$m$$ is slots.

Problem: Can you please help me to prove that if $$k$$ was the $$(i +1)$$st key inserted into the hash table, the expected number of probes made in a search for k is at most $$1/(1 − (i)/m) = m/(m − i)$$? Should it be that $$1/(1 − (i+1)/m) = m/(m − (i+1))$$ please?