# Sum of 'the first k' binomial coefficients for fixed $N$

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?

• 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$ ' . Oct 1, 2017 at 9:45
• 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. May 2, 2019 at 19:31
• *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 May 2, 2019 at 19:49

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

• 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 Mar 6, 2010 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 Mar 27, 2010 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 Mar 27, 2010 at 17:04
• 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... Sep 20, 2018 at 15:59

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]

• I like this plot. It's a shame that Gallier doesn't include the proof. Aug 31, 2010 at 22:15
• Yeah, the proof he refers to is actually for a different bound (although it seems numerically close) Aug 31, 2010 at 23:07
• Here's Lovasz proof, turns out it's in Chapter 3, not Chapter 5 yaroslavvb.com/upload/lovasz-proof2.pdf Sep 1, 2010 at 2:19

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.

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.

• 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)$$ Oct 4, 2011 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... Oct 4, 2011 at 0:59

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

Copy on my site

• Could you please include a reference to you paper more precise than "old"? Nov 11, 2015 at 16:21
• That is very nice - but isn't it different then the original question? Aug 5, 2017 at 20:08
• @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$$ Aug 5, 2017 at 22:42
• @მამუკაჯიბლაძე: I think I see what you mean, but I think also, you forgot a term? Aug 14, 2017 at 18:01

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$

• Actually the entire sum turns out to be upper bounded by $(eN/k)^k$ Sep 17, 2015 at 21:50
• 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$$ Apr 13, 2017 at 18:26
• Is $e$ the euler constant? Aug 5, 2017 at 20:16
• @Make, $e$ is the base of natural logarithms, $2.718281828459045\dots$. Aug 5, 2017 at 23:22
• @Make42 The proof by Joe Dohn doesn't show explicitly the use of $e$ but here it is: $$\sum_{i=0}^k \frac{k^i}{i!} (N/k)^i \leq \sum_{i=0}^k \frac{k^i}{i!} (N/k)^k =(N/k)^k \sum_{i=0}^k \frac{k^i}{i!} \leq (N/k)^k \sum_{i=0}^\infty \frac{k^i}{i!} =(N/k)^k e^k.$$ Mar 21, 2021 at 23:33

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.

• 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. Mar 6, 2010 at 3:32
• 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. Aug 5, 2017 at 23:34

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

• Probably the relevant page in A=B is p. 102. The book is available online: math.upenn.edu/~wilf/Downld.html
– user21349
Aug 14, 2018 at 14:54

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.

• 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). Jun 10, 2015 at 19:40

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.

A relevant fact, which has not been mentioned, not explicitly at least: the integral remainder formula in the Taylor expansion, $$\sum_{i=0}^k{N\choose i}=2^N- N{N-1\choose k}\int_0^1(1+t)^{N-k-1}(1-t)^kdt=$$ $$=2^N\bigg[1- N{N-1\choose k}\int_0^{\frac12}\Big(\frac12+s\Big)^{N-k-1}\Big(\frac12-s\Big)^kds\bigg].$$

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*}

Since you are interested in information theory you might want to consider the following bound. In the limit of large N and setting k/N = p, there is a simple trick (I learned it from "Information, Physics and Computation", by Mezard and Montanari, but it seems to be well known in the Statistical physics community):

$${N \choose k} \sim 2^{N H_2(p)}$$

where $$H_2(p) = -p\log_2(p) - (1-p)\log_2(1-p)$$ is the binary entropy function. You can do most of the computations from this approximation (it serves also as upper bound for $$6\leq Nk(N-k)$$) and get rather simple results, but if you want to be more precise you can work out with Stirling's approximation and get

$$\frac{2\pi}{e}\sqrt{\frac{1}{Np(1-p)}} 2^{N H_2(p)} \leq {N \choose k} \leq \frac{e}{2\pi}\sqrt{\frac{1}{Np(1-p)}} 2^{N H_2(p)}$$

In the case where $$p<1/2 \iff k< N/2$$, you can move to calculus and get the upper bound

$$\sum_{i=0}^{k}{N \choose k} \leq \frac{e}{2\pi}\sqrt{\frac{1}{Np(1-p)}} \sum_{i=0}^{k} 2^{N H_2(k/N)} \approx \frac{e}{2\pi}\sqrt{\frac{1}{Np(1-p)}} \int_{x=0}^p 2^{N H_2(x)}dx$$

and the integral can be approximated by setting $$H_2(x)\leq H_2(p) + \left.\frac{dH_2(x)}{dx}\right|_{x=p}(x-p) = H_2(p) + r (x-p)$$, where $$r = -\log_2{\frac{p}{1-p}}$$. Then

$$\int_{x=0}^p 2^{N H_2(x)}dx \leq 2^{N H_2(p)-Nrp}\int_{x=0}^p 2^{Nrx}dx = 2^{N H_2(p)} \dfrac{p^2}{1-p} \dfrac{1-\left(\frac{p}{1-p}^{-pN}\right)}{N\log_2\left(\frac{p}{1-p}\right)}$$.

Note that the approximation becomes better and better with larger $$N$$, because most of the mass of the integral is at the approximation point. With large $$k$$, $$\sum_{i=0}^{k}{N \choose k} \leq \frac{e}{2\pi}\left(\frac{p}{N(1-p)}\right)^{\frac{3}{2}} \log_2^{-1}\left(\frac{p}{1-p}\right)2^{N H_2(p)}$$

which corresponds to having the exponential integral having $$-\infty$$ as lower bound.

If $$k>N/2$$, we can solve this by Laplace's method, which is very similar but it considers the case where the approximation is done at $$p=1/2$$, since that's the region that contains most of the mass. Then we can just make the calculation

$$\int_{x=0}^p 2^{N H_2(x)}dx \leq 2^{N}\int_{x=0}^p e^{N \ln(2)\left.\frac{d^2H_2(x)}{dx^2}\right|_{x=1/2}(x-0.5)^2}dx = 2^{N}\int_{x=0}^p e^{-4N(x-0.5)^2}dx = 2^{N}\Phi\left(4N(p-0.5)\right)$$

where $$\Phi$$ is the CDF of the Gaussian distribution. Again, when $$N$$ is large and $$p-0.5\gg1/N$$, $$\Phi\left(4N(p-0.5)\right)$$ is almost $$1$$, so we can ignore it. Then, the whole thing convergest to $$2^N$$, which simply means that most of the mass on thas sum is on the central values ($$k\approx N/2$$).

Two bounds that work uniformly for all $$k$$: $$f(n,k) \leq \binom{n+1}{k} + \binom{n+k-1}{k-1},$$ $$f(n,k)\leq \binom{n+k}{k},$$ where the former is tighter for $$k\geq 2$$.

For a proof, see this answer.

A nice result in probability is Tusnady's inequality. If $$B$$ has binomial distribution $$(n,1/2)$$ then there exists $$Z\sim N(0,1)$$ such that almost surely $$|B - \frac n2 - \frac{\sqrt{n}}{2}Z| \le 1 + \frac{Z^2}{8}.$$ The recent paper An improvement of Tusnády’s inequality in the bulk by Frédéric Ouime (https://arxiv.org/abs/2010.15917)gives a literature review of this inequality with a few recent refinements, e.g., Tusnady's inequality, 24 years later by Massart (http://dx.doi.org/10.1016/S0246-0203(02)01130-5) reduces the constant 1 to $$3/4$$.

The above coupling between $$B$$ and $$Z$$ is obtained through the quantile transform $$B=F^{-1}\circ\Phi(Z)$$ where $$F^{-1}$$ is the generalized inverse of the cdf of the binomial.

The upper bound $$1+Z^2/8$$ (or its refinement) follows from upper and lower bounds on the binomial cumulative distribution function, which is the topic of the question. For instance eq (1.2) in the aforementioned reference Massart (2002) gives, for $$(n+j)/2$$ integer, $$P(B \le (n-j)/2) = P(B \ge (n+j)/2) \le P\Big[ \frac{\sqrt n}{2} Z \ge \frac{j}{2} - \frac{3}{4} \Big].$$ Finding explicit upper bounds in terms of $$j$$ requires upper bounds on the standard normal cdf. For instance, $$P(Z>t) \le \frac{\exp(-t^2/2)}{(2\pi t^2 + 4)^{1/2}}$$ applied to $$t=\frac{j}{\sqrt n} - \frac{3}{2\sqrt n}$$ gives $$\frac{1}{2^n}\sum_{i\le (n-j)/2} \binom{n}{i} = P(B\ge (n+j)/2) \le \frac{\exp(-\frac{(j-3/2)^2}{2n})}{(2\pi(j - 3/2)^2/n + 4)^{1/2}}.$$