11
$\begingroup$

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

$\endgroup$
2

2 Answers 2

17
$\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$
2
  • $\begingroup$ Nice, I didn't know about the upper bound. That's probably as well as you can do, with such simple estimates. $\endgroup$ Feb 5, 2017 at 15:41
  • $\begingroup$ I like the word "popular". :) $\endgroup$
    – Wolfgang
    Feb 6, 2017 at 15:03
13
$\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 https://www.sciencedirect.com/science/article/pii/S0012365X12000544 ( Gottlieb, Lee-Ad; Kontorovich, Aryeh; Mossel, Elchanan, VC bounds on the cardinality of nearly orthogonal function classes, Discrete Math. 312, No. 10, 1766-1775 (2012). ZBL1242.05050.)

$\endgroup$
1
  • $\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 OT
    Aug 6, 2019 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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