# 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$ ' . – Peter Heinig Oct 1 '17 at 9:45
• See also here: math.stackexchange.com/q/1610438/29780 – Erel Segal-Halevi Sep 18 '18 at 6:21
• 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. – Dmitry Vaintrob May 2 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 – Dmitry Vaintrob May 2 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 – 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
• 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... – Martin Hairer Sep 20 '18 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)

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]

• 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 yaroslavvb.com/upload/lovasz-proof2.pdf – Yaroslav Bulatov Sep 1 '10 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)$$ – J. M. is not a mathematician 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. is not a mathematician Oct 4 '11 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"? – Lutz Mattner Nov 11 '15 at 16:21
• @Lutz: Links added. – Brendan McKay Nov 11 '15 at 23:25
• That is very nice - but isn't it different then the original question? – Make42 Aug 5 '17 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 '17 at 22:42
• @მამუკაჯიბლაძე: I think I see what you mean, but I think also, you forgot a term? – Make42 Aug 14 '17 at 18:01

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. – Douglas S. Stones Mar 6 '10 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. – Brian Hopkins Aug 5 '17 at 23:34

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$ – Thomas Dybdahl Ahle Sep 17 '15 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$$ – Joe Dohn Apr 13 '17 at 18:26
• Is $e$ the euler constant? – Make42 Aug 5 '17 at 20:16
• @Make, $e$ is the base of natural logarithms, $2.718281828459045\dots$. – Gerry Myerson Aug 5 '17 at 23:22

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

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.

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

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