# How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n}$ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any idea how to show it. I tried some basic approximations but nothing worked. Thanks for your help.

• Divide both sides by $2^{2n}$, now the left hand side is the probability that if you flip $2n$ coins you will get heads fewer than $.999n$ times. From here the key thing to look up is Chebyshev's inequality, and probably Sterling's approximation. Good luck. – Nate Mar 5 '14 at 20:26

With $X \sim B(2n, 1/2)$, we have by Chernoff bound,
$$P(X\leq 0.999n) \leq \exp\left( -10^{-6} n \right).$$
On the other hand, by Stirling's formula, $$P(X=n) \sim \frac 1{2^{2n}} \frac{\sqrt{2\pi \cdot 2n} \left( \frac {2n}e \right)^{2n}}{(\sqrt{2\pi n} )^2 \left(\frac ne\right)^{2n} } \sim \frac 1{\sqrt{\pi n}}.$$ Thus, for sufficiently large $n$, we have $$P(X\leq 0.999n)< P(X=n).$$
We can avoid Chernoff bound and Stirling's formula, and prove this in a completely elementary way. As @Nate suggested, we apply Chebyshev inequality. $$P(X\leq 0.999n)=\frac 12 P( |X- n|\geq 0.001n ) \leq \frac 12 \cdot \frac {\mathrm{Var}(X)}{(0.001n)^2} = \frac {250000 }n.$$ For the central probability, use $$P(X=n)=\frac1{2^{2n}} \frac{(2n)!}{n!n!}=\frac{ 1 \cdot 3 \cdots (2n-1)}{2 \cdot 4 \cdots 2n}.$$ Then by squaring, we have $$P(X=n)^2 = \left( \frac 12\right)^2 \left( \frac 34 \right)^2 \cdots \left(\frac{2n-1}{2n}\right)^2.$$ Then replace $\left(\frac 34\right)^2$ by $\frac 23 \cdot \frac 34$, and $\left(\frac 56\right)^2$ by $\frac 45\cdot \frac 56$, $\ldots$, lastly $\left(\frac{2n-1}{2n}\right)^2$ by $\frac{2n-2}{2n-1}\cdot\frac{2n-1}{2n}$. This gives $$P(X=n)^2 \geq \frac 12 \cdot \frac 1{2n}=\frac1{4n}.$$ Now, we have $$P(X=n)\geq \frac 1{2\sqrt n}.$$ Therefore, for $n> 500000^2$, we have $$P(X\leq 0.999n)< P(X=n).$$