I was given a task about hash tables, to prove that for a hash table with n buckets and separate chaining collision resolution the probability of collision occurrence within $\theta(\sqrt{n})$ inserts is more that $\frac{1}{2}$.
From basic probability theory I've come to the following inequality describing probability of collision occurrence within $j$ inserts: $$1\cdot\Big(1-\frac{1}{n}\Big)\cdot\Big(1-\frac{2}{n}\Big)\cdot ... \cdot \Big(1-\frac{j-2}{n}\Big)\cdot\Big(1-\frac{j-1}{n}\Big) \geq \frac{1}{2},\ for\ j=\theta(\sqrt{n})$$ But I've been struggling a lot with this and unable to solve it. Do you have any ideas? Have been thinking about plots and exponent, unfortunately with no result
Hint: Try to use following assumption from Taylor's series expansion: $e^x \geq x+1$.