9
$\begingroup$

Let $n$ be a positive integer. Prove that \begin{align} \sum_{k=0}^n \left(-1\right)^k \binom{n}{k} = 0 . \end{align}

I tried to solve it using induction, but that got me nowhere. I think the easiest way to prove it is to think of a finite set of $n$ elements, but I can't find the solution.

$\endgroup$
  • 1
    $\begingroup$ Note that both proofs below fail for $n=0$. $\endgroup$ – Carsten S Dec 18 '13 at 15:22
  • 2
    $\begingroup$ @CarstenSchultz Because $$\sum_{k=0}^0 (-1)^k\binom{0}{k} = 1,$$ the result doesn't hold for $n = 0$. $\endgroup$ – Daniel Fischer Dec 18 '13 at 15:48
  • $\begingroup$ @DanielFischer, I am aware of that ;) But I do not know, if $0$ is in Franck's $\mathbb N$. $\endgroup$ – Carsten S Dec 18 '13 at 16:58
  • $\begingroup$ doesn't $\mathbb N$ start at 1? $\endgroup$ – FranckN Dec 18 '13 at 17:00
  • 2
    $\begingroup$ @FranckN There are different conventions. Some let $\mathbb{N}$ start with $0$, some with $1$. Given the problem statement, it is overwhelmingly likely that the problem author belongs to the latter group. $\endgroup$ – Daniel Fischer Dec 18 '13 at 17:02
24
$\begingroup$

Using Binomial Theorem for positive integer exponent $n$

$$(a+b)^n=\sum_{0\le r\le n}\binom nr a^{n-r}b^r$$

Set $\displaystyle a=1,b=-1$ in the above identity

$\endgroup$
18
$\begingroup$

I think the easiest way to prove it is to think of a finite set of $n$ elements,

If you think of it that way, it's the number of even sized ($(-1)^k = 1$) subsets of $\{1,\,\dotsc,\,n\}$ minus the number of odd-sized ($(-1)^k = -1$) subsets.

The map

$$\varphi \colon S \mapsto \begin{cases} S\cup \{1\} &, 1 \notin S\\ S \setminus \{1\} &, 1 \in S \end{cases}$$

that "flips $1$", i.e. adds $1$ to $S$ if $1\notin S$ and removes it if $1\in S$, is a bijection between the set of even-sized and the set of odd-sized subsets. Thus $\{1,\, \dotsc,\,n\}$ has as many even-sized subsets as odd-sized, i.e.

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

for all $n \geqslant 1$.

$\endgroup$
  • $\begingroup$ but what happen if n its an odd number? I think it doesn't apply $\endgroup$ – FranckN Dec 18 '13 at 14:55
  • $\begingroup$ Take a subset $S$ that doesn't contain $1$. If $S$ has an odd number of elements, then $S\cup \{1\}$ has an even number of elements, and vice versa. $\endgroup$ – Daniel Fischer Dec 18 '13 at 14:58
6
$\begingroup$

Please allow me to give a less direct proof. Let $p$ be the product of $n$ different primes $q_1,\ldots,q_n$.

We know $$\sum_{d \mid p}\mu(d)=0,$$ where $\mu$ is the Möbius function.

Each divisor $d$ of $p$ is the product of primes from the set $\{q_1,\ldots,q_n\}$, and will satisfy $\mu(d)=1$ or $\mu(d)=-1$, depending on the parity of the number of primes dividing $d$.

It follows that there as many ways to choose an odd number of primes as ways to choose an even number of primes.

Equivalently, $$\sum_{0\leq 2k \leq n}\binom{n}{2k}=\sum_{0\leq 2k+1 \leq n}\binom{n}{2k+1},$$ it follows that $$\sum_{k=0}^n\binom{n}{k}(-1)^k=0.$$

$\endgroup$
2
$\begingroup$

As this question just got revived, I thought I'd add another bijective proof. Namely, we are trying to show that the number of subsets of $\{1,2,\dots,n\}$ with an odd number of elements is equal to the number of subsets with an even number of elements. To that end, given any subset $S$, just take the symmetric difference with $\{1\}$, i.e. $S\to S\triangle \{1\}$.

$\endgroup$
2
$\begingroup$

Here is a different tack: If you drop the term for $k=0$, this sum is the negation of the Euler characteristic of the $n$-dimensional simplex, whose faces of dimension $k$ correspond to subsets of ${0,...,n}$ with cardinality $k+1$. The simplex is a contractible space, so its Euler characteristic is the same as that of a point, namely 1. Putting back in the term for $k=0$, we see that the original sum is 1-1=0.

This is way more work than necessary (appealing to homotopical invariance of the Euler characteristic), but it's fun, and it's suggestive of the idea that alternating sums can sometimes be dealt with topologically.

$\endgroup$
1
$\begingroup$

Even though this question is pretty old, and the OP probably will not see the answer, I think it's worthwhile to provide a proof by induction, which the OP (and maybe others) had problems with and surprisingly no one has posted yet.


Since the statement is true for $n=1$, suppose it holds for $n=m$. Then the statement for $n=m+1$ follows from $$\require\cancel \sum_{k=0}^{m+1} (-1)^k {m+1 \choose k} =\sum_{k=0}^{m} (-1)^k {m \choose k} \\ \cancel{{m \choose 0}-{m+1 \choose 0}}+\sum_{k=1}^{m} (-1)^k {m \choose k}-(-1)^k{m+1 \choose k}-(-1)^{m+1}{m+1 \choose m+1}=0 \\ \sum_{k=1}^m (-1)^{k+1}\left({m+1 \choose k}-{m \choose k}\right)+(-1)^{m+2}{m+1 \choose m+1}=0,$$ which, recalling the property $\displaystyle {a \choose b}+{a \choose b+1}={a+1 \choose b+1},$ is equivalent to $$\sum_{k=1}^m (-1)^{k+1} {m \choose k-1}+(-1)^{m+2}{m+1 \choose m+1}=0 \\ \sum_{k=0}^{m-1} (-1)^{k} {m \choose k}+(-1)^{m}{m \choose m}=0 \\ \sum_{k=0}^{m} (-1)^k {m \choose k}=0,$$ and this is is precisely our inductive hypothesis.

$\endgroup$
1
$\begingroup$

Alternatively, prove a more general identity below: $$\sum_{r=0}^k\,(-1)^r\binom{n}{r}=(-1)^k\binom{n-1}{k}\,,$$ for all integers $n,k\geq 0$. When $k=n$, we have $$\sum_{r=0}^{n}\,(-1)^r\binom{n}{r}=(-1)^n\binom{n-1}{n}=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.