MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in the function $\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?

share|cite|improve this question

11 Answers 11

up vote 30 down vote accepted

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} \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)}. $$

share|cite|improve this answer
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 – Gerhard Paseman Mar 6 '10 at 8:03
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 – Gerhard Paseman Mar 27 '10 at 17:00
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 – Gerhard Paseman Mar 27 '10 at 17:04

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)

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.

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]
share|cite|improve this answer
I like this plot. It's a shame that Gallier doesn't include the proof. – Michael Lugo Aug 31 '10 at 22:15
Yeah, the proof he refers to is actually for a different bound (although it seems numerically close) – Yaroslav Bulatov Aug 31 '10 at 23:07
Here's Lovasz proof, turns out it's in Chapter 3, not Chapter 5 – Yaroslav Bulatov Sep 1 '10 at 2:19

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.

share|cite|improve this answer
I would not be so harsh in saying that the hypergeometric form is "not useful"; for instance, one can apply a Pfaff transformation, , 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)$$ – J. M. Oct 4 '11 at 0:57
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... – J. M. Oct 4 '11 at 0:59

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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. – Douglas S. Stones Mar 6 '10 at 3:32

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).

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer
Actually the entire sum turns out to be upper bounded by $(eN/k)^k$ – Thomas Dybdahl Ahle Sep 17 '15 at 21:50

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

share|cite|improve this answer
Could you please include a reference to you paper more precise than "old"? – Lutz Mattner Nov 11 '15 at 16:21
@Lutz: Links added. – Brendan McKay Nov 11 '15 at 23:25

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.

share|cite|improve this answer
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). – The Masked Avenger Jun 10 '15 at 19:40

I'm not sure but i think there might be an alternative approach , please correct me if i'm wrong. By vandermondes identity we have

$$\begin{pmatrix} n+k\\ k \end{pmatrix}=\sum_{j=0}^{k}{\begin{pmatrix} n\\ j \end{pmatrix}\begin{pmatrix} k\\ k-j \end{pmatrix}}=\sum_{j=0}^{k}{\begin{pmatrix} n\\ j \end{pmatrix}}*\sum_{j=0}^{k}{\begin{pmatrix} k\\ j \end{pmatrix}}$$

The term in the middle basically represents a convolution so we make use of cauchy product to reduce it and the sum $$\sum_{j=0}^{k}{\begin{pmatrix} k\\ j \end{pmatrix}}=2^{k}$$


$$\begin{pmatrix} n+k\\ k \end{pmatrix}=2^{k}\sum_{j=0}^{k}{\begin{pmatrix} n\\ j \end{pmatrix}}$$

and hence $$2^{-k}\begin{pmatrix} n+k\\ n \end{pmatrix}=\sum_{j=0}^{k}{\begin{pmatrix} n\\ j \end{pmatrix}}$$

The term on the left when summed over k = 0 through n reduces to $2^{n}$

share|cite|improve this answer
Your formula already fails for $n=k=2$ because $\binom 42=6$ but $\binom 20+\binom 21+\binom 22=4$. – Sebastian Goette Nov 27 '15 at 22:15
Did you even check this in the simplest cases? Please delete this answer. – Todd Trimble Nov 28 '15 at 0:55
The mistake is already at the second equation sign - a convolution is not the product of the totals. – Sebastian Goette Nov 28 '15 at 10:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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