Approximation of Binomial Coefficients

A proof that $\frac{1}{2}\frac{n^k}{k!}\lt{n\choose k}$.

In a blog post, rjlipton proves that $$\frac{1}{4}\frac{n^k}{k!}\le{n \choose k}\le\frac{n^k}{k!}$$ when $k\le\sqrt{n}$. I posted a comment trying to strengthen the first inequality to $$\frac{1}{2}\frac{n^k}{k!}\lt{n \choose k}$$ That comment is almost unreadable because (1) I don't know how to use LaTeX on wordpress, (2) especially if I get only one try (can't edit). Here, I don't have such problems.

Proof. Consider a hashtable with $n$ buckets and $k$ items. There are $n^k$ ways to distribute the items, out of which ${n \choose k}k!$ have no collision. The probability of having some collision is $1 - {n \choose k}k!/n^k$. Now suppose $Y$ is a random variable whose value says how many collisions there are. So, $$P(Y\gt 0)=1-\frac{{n \choose k}}{n^k/k!} \le \mathop{\rm E} Y$$ The inequality comes from the first moment principle. The expected number of collisions increases with $k$, so we just look at the case $k=\sqrt{n}$. There are $\sqrt{n}(\sqrt{n}-1)/2$ possible collisions, each happening with probability $1/n$. Thus, $$\mathop{\rm E}Y=\frac{\sqrt{n}(\sqrt{n}-1)}{2}\frac{1}{n}=\frac{1}{2}-\frac{1}{2\sqrt{n}}$$ Putting the previous two displayed inequalities together, we get $$1-\frac{{n \choose k}}{n^k/k!}\le\frac{1}{2}-\frac{1}{2\sqrt{n}}$$ and finally $$\frac{{n \choose k}}{n^k/k!} \ge \frac{1}{2}+\frac{1}{2\sqrt{n}} \gt \frac{1}{2}$$

Update: Stefan Kiefer pointed out that the tight bounds are $$\frac{1}{\sqrt{e}}\frac{n^k}{k!}\lt{n \choose k}\le\frac{n^k}{k!}\qquad\text{if $k\le\sqrt{n}$}$$