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

Question

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?

Answer 1

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

Answer 2

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]

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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$

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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.

Answer 15

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