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?



Sum of 'the first k' binomial coefficients for fixed $N$
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)}.$$


