# Bounding sum of binomials

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)$?

-

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.$$
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.