Summation of $\binom{N}{K}$

Question

I was working on a math problem that required me to figure out the general summation of $\binom{N}{0} + \binom{N}{1} + \ldots + \binom{N}{K}$.

I know that if $k = N$, the answer is $2^N$. But is there an answer for a general $k$?

For reference, this is the problem:

How many $N$-bit binary strings contain anywhere from none to $\frac{N}{2}$ zeros (inclusive)? $N$ is even.

The answer involves recognizing that all possible combinations of strings that have zeroes can be represented by $\binom{N}{0} + \binom{N}{1} + \ldots + \binom{N}{N}$, and that representing the answer to the problem (anywhere from $0$ to $\frac{N}{2}$ zeroes) would be $\binom{N}{0} + \binom{N}{1} + \ldots + \binom{N}{N/2}$.

Hence my question.

Answer 1

Recall that $${n \choose k}={n \choose n-k}$$

Hence $$\sum_{k=0}^{n/2} {n \choose k}=\sum_{k=0}^{n/2} {n \choose n-k}=\sum_{k=n/2}^n {n \choose k}$$

Therefore $$2^n=\sum_{k=0}^n {n \choose k}=\sum_{k=0}^{n/2} {n \choose k}+\sum_{k=n/2 +1}^n {n \choose k}=\sum_{k=0}^{n/2} {n \choose k}+\sum_{k=n/2}^{n} {n \choose k}-{n \choose n/2}=2\sum_{k=0}^{n/2} {n \choose k}-{n \choose n/2}$$

Which gives $$\sum_{k=0}^{n/2} {n \choose k}={2^{n} +{n \choose n/2} \over 2}$$

Answer 2

Your question is more easily answered more directly, without recourse to a formula for more general $k$. The number of $N$-bit strings with $N/2$ zero bits, with $N$ even, is

$$ S_{N/2} = \binom{N}{N/2} $$

Of the remaining strings, exactly half have fewer than $N/2$ zero bits, because the other half have one's complements that have fewer than $N/2$ zero bits. Thus, the total number of $N$-bit songs with up to $N/2$ zero bits is

$$ S = \frac{2^N-S_{N/2}}{2}+S_{N/2} = 2^{N-1}+\frac{S_{N/2}}{2} $$

For example, for $N = 4$, we have a total count of

$$ S = 2^3 + \frac{1}{2} \binom{4}{2} = 8+3 = 11 $$

and sure enough, the set $\{1111, 1110, 1101, 1011, 0111, 1100, 1010, 1001, 0110, 0101, 0011\}$ has $11$ elements.

Answer 3

There is no closed form formula for that sum, I do not know how to prove it but there is a proof of this fact in chapter 4.2 of a Course in Enumeration by Martin Aigner.

Answer 4

Curiously, if the signs are alternating, then there is a closed form for a general $k$ i.e.

$$\sum_{r=0}^{k} (-1)^r\binom Nr=\binom N0-\binom N1+\binom N2-\cdots+(-1)^k\binom Nk=(-1)^k\binom {N-1}k$$

See this: Bonferroni Inequalities.