19
$\begingroup$

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?

$\endgroup$
48
$\begingroup$

Here is an alternate way:

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

by the binomial theorem.

$\endgroup$
25
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you please explain the right side of the equation? $\endgroup$ – Lola Jan 11 '17 at 11:40
13
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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