## Sum of ‘the first k’ binomial coefficients for fixed n

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?

-

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

-
 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 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 – Gerhard Paseman 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 – Gerhard Paseman Mar 27 2010 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]

-
 I like this plot. It's a shame that Gallier doesn't include the proof. – Michael Lugo Aug 31 2010 at 22:15 Yeah, the proof he refers to is actually for a different bound (although it seems numerically close) – Yaroslav Bulatov 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 – Yaroslav Bulatov Sep 1 2010 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.

-
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. 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... – J. M. Oct 4 2011 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.

-

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 - x*y)/((1 - y - x*y)*(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 2010 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).

-

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

-

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.

-

All of the above regarded estimating an upper bound for the sum.

I am interested in estimating a lower bound for the sum.

Dag

-
 Please post new questions as separate questions – Yemon Choi Jun 30 2011 at 0:12 See mathoverflow.net/questions/55585/… . – Emil Jeřábek Jun 30 2011 at 10:57