# Asymptotics for a partial sum of binomial coefficients

Good afternoon,

I would like to ask, if anyone knows how to evaluate a sum

$$\sum_{k=0}^{\lambda n}{n \choose k}$$

for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better.

In Concrete Mathematics (Graham, Knuth, Patashnik), it is shown how to evaluate this sum with absolute error $O(1)$, but it is not clear to me, how to obtain better absolute error in a straightforward manner.

#### Solutions Collecting From Web of "Asymptotics for a partial sum of binomial coefficients"

This is more of an extended comment than an answer, but you may find it useful.

In Exercise 9.42 of Concrete Mathematics (page 492 in the second edition),
the authors establish the asymptotic formula
$$\sum_{k=0}^{\lambda n} {n\choose k}=2^{n H(\lambda)-\lg(n)/2+O(1)}$$
where $0<\lambda< 1/2$,
$H(\lambda)= \lambda \lg({1\over \lambda})+(1-\lambda)\lg({1\over 1-\lambda})$, and
$\lg$ is the binary logarithm.

The sum on the left is a small fraction of the full sum $2^n$.
Note that this is a multiplicative approximation, the ratio of the
sum and the approximation remains bounded as $n\to\infty$, not the difference.

Their result has an interpretation using probability.
Write
$$\sum_{k=0}^{\lambda n} {n\choose k} =2^n\,\mathbb{P}(X_n/n\leq \lambda)$$
where $X_n$ is a binomial$(n,1/2)$ random variable.
The theory of large deviations suggests an approximation
$$\mathbb{P}(X_n/n\leq \lambda)\approx \exp(-nI(\lambda))$$
where $I$ is the rate function $I(x)=x\log(x)+(1-x)\log(1-x)+\log(2)$.
This gives the leading factor in their approximation; they also divide by $\sqrt{n}$
for further accuracy.

If you are willing to use the standard normal distribution function
$\Phi(z)=\mathbb{P}(Z\leq z)$, then by the central limit theorem,
we have
$$\mathbb{P}(X_n\leq \lambda n) =\mathbb{P}\left({X_n-n/2\over\sqrt{n/4}}\leq {\lambda n-n/2\over\sqrt{n/4}} \right) \approx\mathbb{P}\left(Z\leq \sqrt{n}(2\lambda-1) \right).$$
In other words, we have the approximation
$$\sum_{k=0}^{\lambda n} {n\choose k} =2^n\, \Phi(\sqrt{n}(2\lambda-1)).$$
This seems to be at least as
accurate as the Concrete Mathematics approximation,
and you can get more accuracy by using the “continuity correction”.

More detailed asymptotic results for binomial tails can be found in this paper by
Andrew Carter and David Pollard. In particular, see Theorem 1. I hope you find what you want there; happy hunting!