Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a small $c>0$, what is a smallest $k$ such that $$\sum_{i=0}^k \binom{n}{i} \ge c \cdot 2^n.$$

The sum jumps somewhere around $k=\frac{n}2$ from $o(2^n)$ to almost $2^n$. Is there a better estimate than $k=\frac{n}{2}+o(n)$?

share|cite|improve this question
up vote 3 down vote accepted

This is called central limit theorem. You ask for $P(S_n\le k)$ to be about $c$, where $S_n$ is binomial $(n,1/2)$. Since $S_n$ has expectation $n/2$ and variance $n/4$, for every fixed $x$, $$ P(S_n\le n/2+x\sqrt{n}/2) $$ converges to $P(Z\le x)$ where $Z$ is centered standard Gaussian. Reasoning backwards, pick $x$ such that $P(Z\le x)=c$, that is, $$ \int_{-\infty}^x\mathrm{e}^{-z^2/2}\mathrm{d}z/\sqrt{2\pi}=c, $$ and choose for $k$ the integer part of $$ n/2+x\sqrt{n}/2. $$

share|cite|improve this answer

Let $X$ be the random variable which represents the result of tossing a fair coin $n$ times. Then $$\sum_{i=0}^k 2^{-n}\binom{n}{i}$$ is the probability that $X \le k$.

This probability is well-approximated by the probability that a normally distributed random variable with mean $n/2$ and standard deviation $\sqrt{n}/2$ is $\le k$. It is convenient to express this probability as usual in terms of the standard normal. We end up with an integral which is relatively easy to approximate, using simple estimates based on integration by parts, or more sophisticated estimates.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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