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

Question

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?

Answer 1

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

Answer 2

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

The binomial theorem strikes again.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.