Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
3  
$\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}$. –  Davide Giraudo Dec 27 '11 at 19:52
    
A generalization: math.stackexchange.com/questions/4175/… –  Mike Spivey Dec 27 '11 at 19:54
    

8 Answers 8

Here is an alternate way:

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

by the binomial theorem.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
I can't resist adding that the same method applied to the permutohedron yields the identity $\sum(-1)^{n-k}k!{n \brace k}=1$ –  Grigory M Jan 15 at 20:20

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.