4
$\begingroup$

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.

$\endgroup$
6
  • 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
    Commented Oct 13, 2015 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
    Commented Oct 13, 2015 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
    Commented Oct 14, 2015 at 0:45
  • $\begingroup$ @joriki you're right, I've changed my question! $\endgroup$
    – Devos50
    Commented Oct 14, 2015 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
    Commented Oct 14, 2015 at 7:26

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented Oct 15, 2015 at 12:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .