9
$\begingroup$

I'd like to compute $\sum_{i=0}^k {{N}\choose{i}}$. Is there a computable approximation for that?

$\endgroup$
14
$\begingroup$

One of the more convenient and popular approximations of the sum is

$$\frac{2^{nH(\frac{k}{n})}}{\sqrt{8k(1-\frac{k}{n})}} \leq \sum_{i=0}^k\binom{n}{i} \leq 2^{nH(\frac{k}{n})}$$

for $0< k < \frac{n}{2}$, where $H$ is the binary entropy function. (The upper bound is exactly what Aryeh Kontorovich mentions.) You can find its proof in many textbooks, but probably I first learned it from Chapter 10 of The Theory of Error-Correcting Codes by MacWilliams and Sloane.

Also, this post on MO asks a similar question and is a good resource for the sum in my opinion. You can find several other useful bounds there.

$\endgroup$
  • $\begingroup$ Nice, I didn't know about the upper bound. That's probably as well as you can do, with such simple estimates. $\endgroup$ – Aryeh Kontorovich Feb 5 '17 at 15:41
  • $\begingroup$ I like the word "popular". :) $\endgroup$ – Wolfgang Feb 6 '17 at 15:03
10
$\begingroup$

A well-known upper bound, for $k\le N/2$, is $$ \sum_{i=0}^k {N\choose i} \le 2^{N H(k/N)},$$ where $H$ is the binary entropy function $$ H(x) = -x\log_2(x)-(1-x)\log_2(1-x).$$ This bound was sharpened in Lemma 5 of http://www.sciencedirect.com/science/article/pii/S0012365X12000544

$\endgroup$
  • $\begingroup$ The sharpening adds a prefactor of $0.98$; the authors comment that a smaller prefactor is possible with a more careful/detailed proof. The paper is also available, open access, on arXiv: arxiv.org/abs/1007.4915; there it is Lemma 7.1, in Section 7 $\endgroup$ – Sam T Aug 6 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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