> 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: <!-- language: lang-cpp --> 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.