Lower bound for sum of binomial coefficients?

First, what the Stirling bound or Stanica's result give is already a $(1+O(n^{-1}))$ approximation of $\binom nk$, hence the only problem can be with the sum. I don't know how to do that with such precision, but it's easy to compute it up to a constant factor by approximating with a geometric series:

$$\sum_{i\le k}\binom ni=\begin{cases}\Theta(2^n)&k\ge n/2-\sqrt n,\\\\\Theta\left(\left(1-\frac{2k}n\right)^{-1}\binom nk\right)&k\le n/2-\sqrt n.\end{cases}$$

More generally,

$$\sum_{i\le k}\binom ni(1-\epsilon)^{n-i}\epsilon^i=\begin{cases}\Theta(1)&k\ge\epsilon n-s,\\\\\Theta\left(\frac{\epsilon(n-k)}{\epsilon n-k}\binom nk(1-\epsilon)^{n-k}\epsilon^k\right)&k\le\epsilon n-s,\end{cases}$$

where $s=\sqrt{n\epsilon(1-\epsilon)}$. Cf. the appendix to my paper http://math.cas.cz/~jerabek/papers/wphp.pdf .

In my paper "On Littlewood's estimate for the binomial distribution", Adv. Appl. Prob., 21 (1989) 475-478, copy at http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf , I find sharp exact bounds on this sum. Taking $p=1/2$ in Theorem 2 gives:

$$B(k; n,1/2) = \sigma \cdot b(k-1,n-1,{1/ 2})\cdot Y({k-n/2\over \sigma})\cdot \exp({E(k; n,1/2)\over \sigma})$$

where:

• $b(k-1; n-1,1/2) = {1\over 2^{n-1}}{n-1\choose k-1}$
• $B(k; n,1/2) = \sum_{j=k}^n b(j; n,1/2) = {1\over 2^n}\sum_{j=k}^n {n\choose j}$
• $Y(x) = Q(x)/\phi(x)$, where:
  • $\phi(x) := {1\over \sqrt{2\pi}} e^{-x^2/2}$
  • $Q(x) := \int_{x}^\infty \phi(u) du $
• $E(k; n,1/2)$ is the error term, which lies between 0 and $\min(\sqrt{\pi/8}, {\sigma/(k-n/2)})$.
• $\sigma = \sqrt{n}/2$.

The relative error is at most $O(n^{-1/2})$ for all $k$, better if $k$ is not close to $n/2$.

The above requires $\frac n2\le k\le n$. For $0\le k\lt \frac n2$, use $B(k;n,p) = 1 − B(n-k+1; n, 1-p)$.

Somewhere on the arXiv there is a paper making numerical comparisons of many such approximations. I can't find it just now, maybe someone else can.

Do you know how good you need it? Provided $k < n/3$ say, a reasonable bound (correct to within a multiplicative factor of 2) is obtained by taking the last term $\binom {n}{k}$ (you see this because you can compute the ratio of each term to the prior term and bound it above by 1/2. Now you can estimate the sum as a geometric series.)

For $\sum_{j < k} \binom{n}{j}a^j(1-a)^{n-j}$, bounding by the last term also works quite well as long as $k$ is a good bit smaller than $an$.