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.

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?

share|improve this question
1  
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. –  Marc van Leeuwen Apr 23 at 3:26
    
Link to an older post –  barto Sep 15 at 18:40

6 Answers 6

up vote 12 down vote accepted

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

share|improve this answer

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

The binomial theorem strikes again.

share|improve this answer
    
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? –  Jason Apr 22 at 22:23
    
Do you know binomial theorem: en.wikipedia.org/wiki/Binomial_theorem? –  Arash Apr 22 at 22:25
1  
Hard to understand why two answers similar to this one - and older - were ignored while this was up voted. –  Git Gud Apr 22 at 22:28
1  
@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$.) –  Steven Taschuk Apr 23 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.

share|improve this answer
    
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}$$ –  John Joy Apr 24 at 14:09

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

share|improve this answer

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

share|improve this answer

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.

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.