# How do I begin proving this binomial coefficient identity: ${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$

This is a homework question.

I'm asked to prove the identity:

$${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$

(The sum ends with ${n\choose n} = 1$, with the sign of the last term depending on the parity of n.)

I recognize that the sequence: $${n\choose 0}, {n\choose 1}, {n\choose 2}, {n\choose 3}$$

corresponds to the binomial coefficients. That is, if I choose $n = 5$, I get the sequence $1, 5, 10, 10, 5, 1$.

Working this out (or just looking at Pascal's triangle), it's obvious that this theorem is true. It looks like the triangle / the binomial coefficients are "symmetric", and so if you add one and subtract one and keep going, it's evident they will cancel out to be zero.

But how do I prove this? Is there a set way? Are there multiple methods for proving this? How should I get started, or what are some names of proving methods I should look into to begin?

• It is not true that for any symmetric sequence if you add terms with alternating signs you always get $0$. Try $(1,3,1)$. It only works if the length is even, which here is trua only in half of the cases. Apr 23, 2014 at 3:26
• Link to an older post Sep 15, 2014 at 18:40

Expand $(1-1)^n$ using the binomial theorem.

What is $(1-1)^n$?

The binomial theorem strikes again.

• That was the answer at the back of the book. But I don't get what just that statement means. Is that a proof to just "say" that? Apr 22, 2014 at 22:23
• Do you know binomial theorem: en.wikipedia.org/wiki/Binomial_theorem? Apr 22, 2014 at 22:25
• Hard to understand why two answers similar to this one - and older - were ignored while this was up voted. Apr 22, 2014 at 22:28
• @Jason Is that a proof to just "say" that? This is perhaps not a complete proof by the standards expected on your homework assignment; it is more of an indication of the key idea of the proof, leaving the details to the reader. (Readers who see those details immediately might consider it a complete proof.) The details: $0 = 0^n = (1+(-1))^n = \sum_{k=0}^n \binom nk 1^{n-k} (-1)^k = \sum_{k=0}^n \binom nk (-1)^k$. (Note, btw, the implicit assumption that $n>0$ in the first step; indeed, the result is false for $n=0$.)
– user21467
Apr 23, 2014 at 2:02

An alternative way when $n$ is odd: It is relatively easy to see "with a set way" that ${n \choose p }= {n \choose n-p}$.

Writing correctly your sum, you can then split it into two parts: the first part where the terms are ${n\choose p}$ for $p<\frac n 2$ and the second part with $p>\frac n2$.

For the case $n$ even, I do not see how adapt this proof.

• i really liked your idea. Suppose $n$ is even. $$S = {n-1\choose 0} - {n-1\choose 1} + \dots + {n-1\choose n-2}- {n-1\choose n-1} = 0$$ $$S-S = {n-1\choose 0} +\sum_{i=1}^{n-1}(-1)^i\bigg({n-1\choose i-1}+{n-1\choose i}\bigg)+{n-1\choose n-1}$$ $$0 = {n\choose 0} +\sum_{i=1}^{n-1}(-1)^i{n\choose i}+{n\choose n}$$ $$0 = \sum_{i=0}^{n}(-1)^i{n\choose i}$$ Apr 24, 2014 at 14:09

Expand: $0 = (1 + (-1))^n$ = ...

Another method is to use the identity $$\binom nk = \binom{n-1}{k-1} + \binom{n-1}{k}$$ If you apply this to each term in the sum, you get \begin{align*} \binom n0 &= \phantom{-}\overbrace{\binom{n-1}{-1}}^{=0} + \binom{n-1}0 \\ -\binom n1 &= -\binom{n-1}0 - \binom{n-1}1 \\ \binom n2 &= \phantom{-}\binom{n-1}1 + \binom{n-1}2 \\ -\binom n3 &= -\binom{n-1}2 - \binom{n-1}3 \\ \binom n4 &= \phantom{-}\binom{n-1}3 + \binom{n-1}4 \\ &\vdots \end{align*} When you add all these up, everything on the RHS cancels.

(A combinatorial way to look at this: your sum being zero means that $\{1,\dotsc,n\}$ has the same number of subsets with an even number of elements as subsets with an odd number of elements. This is true because the even-size subsets can be paired up with the odd-sized subsets: pair up even-size subsets that contain 1 with what you get if you remove the 1, and pair up even-size subsets that don't contain 1 with what you get if you add the 1.)

To answer some of the questions: yes there are multiple ways to prove this, one of which is a "set" way. The obvious way to get started is to ask yourself what facts you know about binomial coefficients. If you are in the privileged position of not knowing very many facts about them, then there a smaller chance to get lost at this stage. You might have heard of a result which has "binomial" in its name.

As for a "set" way to prove this, if you bring all the negative terms to the other side, what you want to prove is $$\binom n0+\binom n2+\cdots = \binom n1+\binom n3+\cdots, \tag{1}$$ in other words that a set $S$ with $n$ element has as many even as odd size subsets. You can prove this by giving a bijection between those collections. Since here you are dealing with two parts of the collection of all subsets of$~S$, an easy way to find such a bijection is to find a parity-flipping operation of subsets that when repeated a second time undoes its own effect. If $n$ is odd, you could take the complement of a subset as operation (this corresponds to the fact that by symmetry of binomial coefficients, as you observed in the question, both sides of $(1)$ contain the same terms, in opposite order, when $n$ is odd), but this fails when $n$ is even, as the parity of the complement does not change then. However the following operation does work for almost all$~n$: if $s_0\in S$ is a specific element, the operation consists of adding $s_0$ to the subset if it was absent, or removing it if is was present. This always changes the parity, and doing it twice in succession gives back the original subset. The only glitch is that you need to choose an element from $S$ for this to work; what to do if there is no such element, in other words $S=\emptyset$? Well in that case there is only one subset (the empty one), and it has an even number of elements, so the result is false. Indeed $(1)$ and your original equation are false for $n=0$; there is no point in trying to prove that case.