# Proving a bound with binomial coefficients

I'm trying to prove the inequality below:

$$\frac{\sum^{n/2 + \sqrt{n}}_{j=0} {n \choose j}}{2^n} \geq 0.95$$

I have no idea where to start. I have tried to fill in the formula for small values of n and I see that it holds but I'm unable to proof this. Can anyone give a hint on how to prove this?

Any help would be greatly appreciated.

• Presumably one wants the upper limit of the sum to be something $\left\lceil \frac{n}{2} + \sqrt{n}\right\rceil$. – Travis Willse Oct 13 '15 at 20:47
• just a suggestion: try finding lower bound on the numerator (it doesn't exist in closed form), perhaps reducing it to Geometric series. – Alex Oct 13 '15 at 21:17
• There shouldn't be a square root in the denominator; the numerator is certainly greater than $0.5\cdot2^n$. – joriki Oct 14 '15 at 0:45
• @joriki you're right, I've changed my question! – Devos50 Oct 14 '15 at 7:15
• check the Travis comment..he is right..because for n=2, it gives $1+\sqrt 2$ which is not an integer..@Devos50 – David Oct 14 '15 at 7:26

This expression can be interpreted as the probability that the number of heads obtained in $n$ tosses of a fair coin is less than or equal to $\mu+2\sigma$, where $\mu=\frac{n}{2}$ and $\sigma=\frac12 \sqrt{n}$ are the expected value and the standard deviation of the number of heads.