78
$\begingroup$

I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other notable properties? Any literature references?

In particular, does it have a closed form or notable algorithm for computing it efficiently?

In case you are curious, this function comes up in information theory as the number of bit-strings of length $N$ with Hamming weight less than or equal to $k$.

Edit: I've come across a useful upper bound: $(N+1)^{\underline{k}}$ where the underlined $k$ denotes falling factorial. Combinatorially, this means listing the bits of $N$ which are set (in an arbitrary order) and tacking on a 'done' symbol at the end. Any better bounds?

$\endgroup$
  • $\begingroup$ Just to add one more $\varepsilon$ of relevant context and interconnectedness: the newest example of these quantities being put to use is Zur Luria's answer to this MO question, given one hour ago. A dictionary 'here:there' is '$i$ : $i$' , '$k$ : $n-1$' , '$0$ : $1$' , ' $N$ : $c$ ' . $\endgroup$ – Peter Heinig Oct 1 '17 at 9:45
  • $\begingroup$ See also here: math.stackexchange.com/q/1610438/29780 $\endgroup$ – Erel Segal-Halevi Sep 18 '18 at 6:21
  • $\begingroup$ You are interested in the dot product of the Fourier series $A(x) = \sum_{j\ge -k} e^{j(ix)}$ and $B(x) = \sum_{j=0}^n \binom{n}{j} e^{j(ix)}.$ There are nice closed forms for both functions, though of course $A(x)$ is singular and should be treated carefully (for example by fudging it and studying $A(x-i\epsilon)$ to get a smooth Fourier series.) The resulting integral will be dominated by its contribution near $x=0;$ depending on $k<<\sqrt{n}$ or $k>>\sqrt{n}$ it will either be a simple or an oscilating integral. $\endgroup$ – Dmitry Vaintrob May 2 at 19:31
  • $\begingroup$ *Sorry, thinking about it some more, both cases will give something rapidly oscillating. If you split up the integrand into a radial and polar part, it should not be too difficult to compute using some standard oscillating integral techniques $\endgroup$ – Dmitry Vaintrob May 2 at 19:49

11 Answers 11

63
$\begingroup$

I'm going to give two families of bounds, one for when $k = N/2 + \alpha \sqrt{N}$ and one for when $k$ is fixed.

The sequence of binomial coefficients ${N \choose 0}, {N \choose 1}, \ldots, {N \choose N}$ is symmetric. So you have

$\sum_{i=0}^{(N-1)/2} {N \choose i} = {2^N \over 2} = 2^{N-1}$

when $N$ is odd.
(When $N$ is even something similar is true but you have to correct for whether you include the term ${N \choose N/2}$ or not.

Also, let $f(N,k) = \sum_{i=0}^k {N \choose i}$.
Then you'll have, for real constant $\alpha$,

$ \lim_{N \to \infty} {f(N,\lfloor N/2+\alpha \sqrt{N} \rfloor) \over 2^N} = g(\alpha) $

for some function $g$. This is essentially a rewriting of a special case of the central limit theorem. The Hamming weight of a word chosen uniformly at random is a sum of Bernoulli(1/2) random variables.

For fixed $k$ and $N \to \infty$, note that $$ {{N \choose k} + {N \choose k-1} + {N \choose k-2}+\dots \over {N \choose k}} = {1 + {k \over N-k+1} + {k(k-1) \over (N-k+1)(N-k+2)} + \cdots} $$ and we can bound the right side from above by the geometric series $$ {1 + {k \over N-k+1} + \left( {k \over N-k+1} \right)^2 + \cdots} $$ which equals ${N-(k-1) \over N - (2k-1)}$. Therefore we have $$ f(N,k) \le {N \choose k} {N-(k-1) \over N-(2k-1)}.$$

$\endgroup$
  • 1
    $\begingroup$ Using the summation formula for Pascal's triamgle, you get a shorter geometric series approximation which may work well for k less than but not too close to N/2. This is (N+1) choose k + (N+1) choose (k-2) + ..., which has about half as many terms and ratio that is bounded from above by (k^2-k)/((N+1-k)(N+2-k)), giving [((N+1-k)(N+2-k))/((N+1-k)(N+2-k) -k^2 +k)]*[(N+1) choose k] as an uglier but hopefully tighter upper bound. Gerhard "Ask Me About System Design" Paseman, 2010.03.06 $\endgroup$ – Gerhard Paseman Mar 6 '10 at 8:03
  • 1
    $\begingroup$ One can take this a step further. In addition to combining pairs of terms of the original sum N choose i to get a sum of terms of the form N+1 choose 2j+c, where c is always 0 or always 1, one can now take the top two or three or k terms, combine them, and use them as a base for a "psuedo-geometric" sequence with common ratio a square, cube, or kth power from the initial common ratio. This will give more accuracy at the cost of computing small sums of binomial coefficients. Gerhard "Ask Me About System Design" Paseman, 2010.03.27 $\endgroup$ – Gerhard Paseman Mar 27 '10 at 17:00
  • 1
    $\begingroup$ When k is so close to N/2 that the above is not effective, one can then consider using 2^(N-1) - c (N choose N/2), where c = N/2 - k. Gerhard "Ask Me About System Design" Paseman, 2010.03.27 $\endgroup$ – Gerhard Paseman Mar 27 '10 at 17:04
  • 1
    $\begingroup$ In the same vein, Cramér's theorem gives you upper and lower bounds of the type $\exp(-J(\alpha)N)$ with an explicit expression for $J$ when $k \approx \alpha N$ and $\alpha < 1/2$. Unless I messed up a quick calculation, one has $J(\alpha) = \alpha \log \alpha + (1-\alpha)\log(1-\alpha)$, but since $J(1/2) = -\log 2$ as expected, it's probably correct... $\endgroup$ – Martin Hairer Sep 20 '18 at 15:59
29
$\begingroup$

Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$

where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$

It seems to be worse than Michael's bound except for large values of k

Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)

(source)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
   Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic]

Edit The proof, Proposition 3.8.2 from Lovasz "Discrete Math".

Lovasz gives another bound (Theorem 5.3.2) in terms of exponential which seems fairly close to previous one

$$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz bound is the top one.

(source)

n = 50;
gallier[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))];
ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Range[0, n/2 - 1]], 
 PlotRange -> All, PlotMarkers -> Automatic]
$\endgroup$
  • $\begingroup$ I like this plot. It's a shame that Gallier doesn't include the proof. $\endgroup$ – Michael Lugo Aug 31 '10 at 22:15
  • $\begingroup$ Yeah, the proof he refers to is actually for a different bound (although it seems numerically close) $\endgroup$ – Yaroslav Bulatov Aug 31 '10 at 23:07
  • 3
    $\begingroup$ Here's Lovasz proof, turns out it's in Chapter 3, not Chapter 5 yaroslavvb.com/upload/lovasz-proof2.pdf $\endgroup$ – Yaroslav Bulatov Sep 1 '10 at 2:19
18
$\begingroup$

One standard estimate when the sum includes about half of the terms is the Chernoff bound, one form of which gives

$$\sum_{k=0}^{(N-a)/2} {N\choose k} \le 2^N \exp\bigg(\frac{-a^2}{2N}\bigg)$$

This isn't so sharp. It's weaker than the geometric series bound Michael Lugo gave. However, the simpler form can be useful.

$\endgroup$
14
$\begingroup$

There is no useful closed-form for this. You can write it down as $$2^N - \binom{N}{k+1} {}_2F_{1}(1, k+1-N, k+2; -1)$$ but that's really just a rewrite of the sum in a different form.

$\endgroup$
  • 5
    $\begingroup$ I would not be so harsh in saying that the hypergeometric form is "not useful"; for instance, one can apply a Pfaff transformation, dlmf.nist.gov/15.8.E1 , to yield the identity $${}_2 F_1\left({{1 \quad m-n+1}\atop{m+2}}\mid-1\right)=\frac12 {}_2 F_1\left({{1 \quad n+1}\atop{m+2}}\mid\frac12\right)$$ $\endgroup$ – J. M. is not a mathematician Oct 4 '11 at 0:57
  • 3
    $\begingroup$ The second bit has an argument that is nearer the expansion center 0 for the Gaussian hypergeometric series, so it stands to reason that the convergence is a bit faster. Also, one no longer needs to add terms of different signs... $\endgroup$ – J. M. is not a mathematician Oct 4 '11 at 0:59
11
$\begingroup$

Here's one from an old paper of mine. It has the property of being precise all the way from the middle to the end. Define $$ Y(x) = e^{x^2/2}\int_x^\infty e^{-t^2/2}dt. $$ Define $x=(2k-n)/\sqrt{n}$. Then for $x\ge 0$, $$\sum_{j=k}^n \binom nj = \sqrt{n} \,\binom{n-1}{k-1} Y(x)\, e^{E(k,n)/\sqrt n},$$ where $0\le E(k,n)\le\min(\sqrt{\pi/2},2/x)$. If $x<0$, use $\sum_{j=k}^n \binom nj=2^n-\sum_{j=n-k+1}^n \binom nj$.

JStor link

Copy on my site

$\endgroup$
  • $\begingroup$ Could you please include a reference to you paper more precise than "old"? $\endgroup$ – Lutz Mattner Nov 11 '15 at 16:21
  • $\begingroup$ @Lutz: Links added. $\endgroup$ – Brendan McKay Nov 11 '15 at 23:25
  • $\begingroup$ That is very nice - but isn't it different then the original question? $\endgroup$ – Make42 Aug 5 '17 at 20:08
  • $\begingroup$ @Make42 You can switch to any of the$$\sum_{j=k}^n\binom nj=\sum_{i=0}^{n-k}\binom ni=2^n-\sum_{j=0}^{k-1}\binom nj$$ $\endgroup$ – მამუკა ჯიბლაძე Aug 5 '17 at 22:42
  • $\begingroup$ @მამუკაჯიბლაძე: I think I see what you mean, but I think also, you forgot a term? $\endgroup$ – Make42 Aug 14 '17 at 18:01
9
$\begingroup$

See A008949 "Triangle of partial sums of binomial coefficients."

$T(n,k) = \sum_{i-0}^k {N\choose i}$ is the maximal number of regions into which $n$ hyperplanes of co-dimension $1$ divide $\mathbb R^k$ (the Cake-Without-Icing numbers)

$2 ~T(n-1,k-1)$ is the number of orthants intersecting a generic linear subspace of $\mathbb R^n$ of dimension $k$. This tells you the probability if you choose $a$ independent random points on the unit sphere in $\mathbb R^d$, the probability that the origin is contained in the convex hull is $T(a-1,a-d-1)/2^{a-1}$. Complementarily, no hemisphere contains all of the points. The null space of the map by linear combinations of the points $\mathbb R^a \to \mathbb R^d$ generically has a kernel of dimension $a-d$, and this intersects the positive orthant iff $0$ is a convex hull of the points. By symmetry, all orthants are equally likely.

$\endgroup$
  • 1
    $\begingroup$ There's a generating function there too: (1 - xy)/((1 - y - xy)*(1 - 2*x*y)). Also, for k=2,3,...,10 it's given by Sloane's A000124, A000125, A000127, A006261, A008859, A008860, A008861, A008862, A008863. $\endgroup$ – Douglas S. Stones Mar 6 '10 at 3:32
  • 1
    $\begingroup$ The $k=5$ case, 1, 2, 4, 8, 16, 31, 57, ... (oeis.org/A000127), is a common "counterexample" in discrete mathematics courses that nice patterns (here, powers of 2) do not always hold. A direct formula is $(n^4 - 6n^3 + 23n^2 - 18n + 24)/24$. An interpretation is the greatest possible number of regions given by drawing secants between $n$ points on a circle. See Honsberger, Martin Gardner, Conway & Guy's Book of Numbers, etc. $\endgroup$ – Brian Hopkins Aug 5 '17 at 23:34
8
$\begingroup$

Each binomial coefficient satisfies $$\left(\frac{N}{i}\right)^i \leq {N \choose i} < \left(\frac{eN}{i}\right)^i,$$ so if $k \leq N/2$, you can upper bound the sum by $k(\frac{eN}{k})^k$

$\endgroup$
  • 7
    $\begingroup$ Actually the entire sum turns out to be upper bounded by $(eN/k)^k$ $\endgroup$ – Thomas Dybdahl Ahle Sep 17 '15 at 21:50
  • 5
    $\begingroup$ For completeness, let me state the proof of that: $$\sum_{i=0}^k \binom{N}{i} \leq \sum_{i=0}^k \frac{N^i}{i!} = \sum_{i=0}^k \frac{k^i}{i!} (N/k)^i \leq e^k (N/k)^k $$ $\endgroup$ – Joe Dohn Apr 13 '17 at 18:26
  • $\begingroup$ Is $e$ the euler constant? $\endgroup$ – Make42 Aug 5 '17 at 20:16
  • $\begingroup$ @Make, $e$ is the base of natural logarithms, $2.718281828459045\dots$. $\endgroup$ – Gerry Myerson Aug 5 '17 at 23:22
7
$\begingroup$

The sum without the $i=0$ term arises in the "egg drop" problem -- see Michael Boardman's article, "The Egg-Drop Numbers," in Mathematics Magazine, Vol. 77, No. 5 (December, 2004), pp. 368-372, which concludes saying, "it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients" with a reference to the book A=B by Petkovsek, Wilf, and Zeilberger (but unfortunately no page reference).

$\endgroup$
6
$\begingroup$

If you interested in some back-of-the-hand order of magnitude estimates, you might consider looking at how $\binom{n}{k}$ behaves when $k=k(n)$ has a certain size. The idea I have in mind is to break down $\sum_{k=0}^m\binom{n}{k}$ into a sum over intervals of $k$ satisfying a certain regime. For example, look at terms where $k=\Theta(n)$, $k=\Theta(n^{1/2})$, etc. In general, using Stirling's approximation, you'll get:

$\binom{n}{k}=\frac{n^ke^k}{k^k\sqrt{2\pi k}} A$

where $A:=\frac{n_{k}}{k^k}=\prod_{i=0}^{k-1}\left(1-\frac{i}{n}\right)$ and $n_k$ is the falling factorial. In particular, it's nicer to work with $B:=\ln(A) = \sum_{i=0}^{k-1} \ln\left(1-\frac{i}{n}\right)$.

Now the idea is that each of the logarithm terms in $B$ can be Taylor expanded up to "sufficient" order depending on the size of $k$ compared to $n$. For example if $k=o(1)$, then $B\approx \sum_{i=0}^{k-1}\approx -\frac{k^2}{2n}$, so you get $A=e^{-\frac{k^2}{2n}(1+o(1))}$. In fact, you can do better than this if you expand $B$ to higher orders. In particular, if $k=o(n^{2/3})$, then $B=\sum_{i=0}^{k-1}-\frac{i}{n}+O(i^2n^{-2})=-\frac{k^2}{2n}+o(1)$ which gives $A=e^{-\frac{k^2}{2n}}(1+o(1))$ where now the $o(1)$ is no longer exponentiated. For other sizes of $k$, the exact same procedure works as long as you expand $B$ to sufficiently high order.

$\endgroup$
5
$\begingroup$

In particular, does it have a closed form or notable algorithm for computing it efficiently?

Is an $O(k)$ algorithm efficient enough? If so, here is a C++ implementation:

unsigned long long sumbincoef( unsigned N, unsigned k ) {
  unsigned long long i, bincoef = 1, sum = 1;
  for( i=1 ; i<=k ; ++i ) {
    bincoef = bincoef * (N-i+1) / i;
    sum += bincoef;
  }
  return sum;
}

Caution: this can overflow for sufficiently large values of $N$ and $k$.

Since one is summing $N\choose i$ for successive $i$, the relevant recursion relation is simply

$${N\choose i} = {N\choose i-1}\frac{N-i+1}{i}$$

so that each term in the sum

$$\sum_{i=0}^k{N\choose i}$$

is calculated from the preceding term in $O(1)$ time.

$\endgroup$
  • $\begingroup$ For small values of k/N, the sum is well approximated by (N+1) choose k, and for slightly larger values by a multiplicative correction of the form (1/(1 - k/N)) . For k near the size of N/c for c an integer not too large, you can use a recursion where the recursive step involves just addition and runs in O(k) time (O(k^2) if you are measuring bit operations). $\endgroup$ – The Masked Avenger Jun 10 '15 at 19:40
1
$\begingroup$

Let $H(N)$ be a random variable representing the number of heads in $N$ fair coin-tosses.

Then, on one hand:

$$\Pr[H(N)\leq k] = {1\over 2^N} f(N,k) $$

On the other hand, by Hoeffding's inequality:

$$\Pr[H(N)\leq (1/2-\epsilon)N] \leq \exp(- 2 N \epsilon^2)$$

Taking $\epsilon = (1/2)-(k/N)$ gives:

$$\Pr[H(N)\leq k] \leq \exp\bigg(-2 N \left({1\over 2} - {k\over N}\right)^2\bigg)$$

Therefore:

\begin{align*} \textbf{(1)} && && f(N,k) \leq 2^N \exp\bigg(-N/2+2k-2k^2/N\bigg) \end{align*}

Another bound that contains a power of two is proved combinatorially here:

$$f(m k + m - 1 ,k) \leq 2^{m k}$$

Substituting $m = {N+1\over k+1}$ gives:

\begin{align*} \textbf{(2)} && && f(N ,k) \leq 2^{(N+1){k\over k+1}} \end{align*}

Above, Joe Dohn proved the following inequality in a comment:

\begin{align*} \textbf{(3)} && && f(N,k) \leq \bigg({e N \over k}\bigg)^k \end{align*}

This Wikipedia page cites the following inequality, where $\epsilon = N/k \leq 1/2$:

\begin{align*} \textbf{(4)} && && \frac{1}{\sqrt{8 N\epsilon(1-\epsilon)}} \cdot 2^{E(\epsilon) \cdot N} \leq f(N,k) \leq 2^{E(\epsilon) \cdot N} \end{align*}

where $E(\epsilon) = -\epsilon\log_2(\epsilon) -(1-\epsilon)\log_2(1-\epsilon)$ is the binary entropy function of $\epsilon$.

Note that $N E(\epsilon) = k \log_2(N/k) + (N-k)\log_2(N/(N-k))$. So the upper bound is:

$$ f(N,k) \leq \bigg({N\over k}\bigg)^k \cdot \bigg({N\over N-k}\bigg)^{N-k} = {N^N \over k^k (N-k)^{N-k}} $$

From Michael Lugo's bound:

$$ f(N,k) \le {N \choose k} {N-k+1 \over N-2k+1},$$

we can get, by letting $f(N,k) = f(N,k+1) - {N \choose k+1}$:

\begin{align*} \textbf{(5)} && && f(N,k) \leq {N \choose k+1} \bigg[ {N-k \over N-2k-1} -1\bigg] ={N \choose k+1}{k+1 \over N-2k-1} \end{align*}

$\endgroup$

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.