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

Show that $$\sum_{k=0}^n(-1)^k\binom nk=0$$ So for odd $n$ we have an even number of terms. So $\binom nk=\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 nk= \binom n0+\sum_{k=1}^{n-1}(-1)^k\binom nk+\binom nn$$ Now $$\sum_{k=1}^{n-1}(-1)^k\binom nk= \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?

• Write out that last sum for some small values of $n$. I think that should make things clearer. – Potato Dec 27 '11 at 19:52
• A generalization: math.stackexchange.com/questions/4175/… – Mike Spivey Dec 27 '11 at 19:54
• – Grigory M Jan 15 '14 at 20:18
• It might be worth mentioning that for $n=0$ the sum is equal to one, not zero. – Martin Sleziak Oct 28 '15 at 17:37

## 8 Answers

Here is an alternate way:

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

by the binomial theorem.

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.

• Can you please explain the right side of the equation? – Lola Jan 11 '17 at 11:40

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$.

For odd $$n$$, the OP gave a bijective proof of the result. The following is a bijective 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.

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.$$

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

One can also give a topological proof of the binomial identity $\sum_{i=0} ^{n} (-1)^i \binom{n}{i}=0$. Consider the standard $(n-1)$-simplex $\Delta^{n-1}$. This has $\binom{n+1}{i+1}$ $i$-simplicies, hence the Euler characteristic of $\Delta^{n-1}$ is $$\chi(\Delta^{n-1})=\sum_{i=0} ^{n-1} (-1)^i \binom{n}{i+1}.$$

The Euler characteristic is homotopy invariant and $\Delta^{n-1}\simeq *$, so we must have

$$\sum_{i=0} ^{n-1} (-1)^i \binom{n}{i+1}=1,$$ or $$\sum_{i=0} ^{n-1} (-1)^i \binom{n}{i+1}-\binom{n}{0}=0$$ since $\binom{n}{0}=1$. Multiplying both sides by $-1$ yields the identity

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

Another approach:

For the difference operator $\Delta f (m) = f(m+1)-f(m)$, the $n$th iteration is

$$\Delta^n f(m)=\sum_{k}(-1)^{n-k}\binom nk f(m+k)$$

Clearly, your sum is the $n$th difference of the constant function $f\equiv 1$, so of course it is zero for $n\ge 1$ because already $f(m+1)-f(m) =0$.