At the end of my previous post I claimed that proving that tends to when tends to infinity and was unpleasant. It appears that I was wrong, and I would like to show here a simple proof that was suggested to me by my colleague Philippe Rigollet.
The key observation is that the term is the probability that an hypergeometric random variable takes value . Hypergeometric distributions are nasty, but when is of larger order than (which is the case here), they are well approximated by a simple binomial . In the present case this suggests the upper bound The latter inequality can be proved formally using the identity Now one can simply use the inequalities and to obtain that the original unpleasant sum is upper bounded by which clearly tends to when tends to infinity and .