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.

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

  • $\begingroup$ I managed to prove it indeed by approximating the Bernoulli distribution I got with a normal distribution. It turned out that the z-score is always 2, giving a probability of at least 0.97. I also assumed that n is large enough for the approximation to make sense. $\endgroup$ – Devos50 Oct 15 '15 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.