Proving $\sum\limits_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$

Question

Show that $$\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$$

So for odd $n$ we have an even number of terms. So $\binom{n}{k} = \binom{n}{n-k}$ which have opposite signs. Thus the sum is $0$.

For even $n$ we have that $$\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = \binom{n}{0}+\sum_{k=1}^{n-1} (-1)^{k} \binom{n}{k} + \binom{n}{n}$$

Now $$\sum_{k=1}^{n-1} (-1)^{k} \binom{n}{k} = \sum_{k=1}^{n-1} (-1)^{k} \left[\binom{n-1}{k} + \binom{n-1}{k-1} \right]$$

What would that sum be in the square brackets?

Answer 1

Here is an alternate way:

$$0=(1-1)^n=\sum_{k=0}^{n} (-1)^{k} \binom{n}{k}$$

by the binomial theorem.

Answer 2

Another way for combinatorially-minded people:

$$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$$

is the number of ways to flip n coins and get an even number of heads, minus the number of ways to flip n coins and get an odd number of heads. Since the parity of the number of heads will always come down to the last coin flipped, and heads/tails are of course equally likely at that point, the sum evaluates to 0.

Answer 3

You should know that $$ (a+b)^n=\sum_{k=0}^n \binom nk a^kb^{n-k}. $$ When $b=1$, this says $$ (1+a)^n=\sum_{k=0}^n \binom nk a^k. $$ So now you just need to consider the case where $a=-1$.

Answer 4

$$0=(1-1)^n=\sum{n\choose k}(-1)^k$$

Answer 5

We have, since $n-1$ is odd \begin{align*}\sum_{k=1}^{n-1}(-1)^k\left[\binom{n-1}k+\binom{n-1}{k-1}\right]&=\sum_{k=1}^{n-1}(-1)^k\binom{n-1}k-\sum_{j=0}^{n-2}(-1)^j\binom{n-1}j\\ &=-1+\binom{n-1}{n-1}(-1)^{n-1}\\ &=-2, \end{align*} hence $$\sum_{k=0}^n\binom nk(-1)^k=\binom n0 -2+\binom nn =0.$$

Answer 6

For odd $n$, the OP gave a bijective proof of the result. The following is a bijecive proof that works for all $n$.

Let $A=\{1,2,\dots, n\}$. Let $\mathcal{E}$ consist of the subsets of $A$ of even cardinality, and let $\mathcal{O}$ consist of the subsets of $A$ of odd cardinality. We produce an explicit bijection $\varphi: \mathcal{E} \to \mathcal{O}$.

If $S\in \mathcal{E}$ and $1\notin S$, let $\varphi(S)=S\cup\{1\}$.

If $S\in \mathcal{E}$ and $1\in S$, let $\varphi(S)=S\setminus\{1\}$.

Comment: For the sake of symmetry, it is probably better to define $\varphi(S)$ as above, but for any subset $S$ of $A$. Then $\varphi$ is an involution on $P(A)$ that interchanges sets of even cardinality with sets of odd cardinality.