3
$\begingroup$

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

Use a combinatorial interpretation of the positive and negative terms.

Edit: I have already proven it using the binomial theorem, more specifically with $(1-1)^n$. I'm having difficulty understanding what is meant by a combinatorial interpretation of the positive and negative terms.


I'm having trouble understanding exactly what is necessary for a combinatorial interpretation. Looking at small cases, I see that the symmetry of the expansion allows us to cancel out lots of terms.

Is this what is meant by a combinatorial interpretation? Is there any resources that introduce the idea of what constitute a combinatorial interpretation? I feel like the professor threw us off in the deep end and I'm trying to keep my head above water with the few problems I have to work with and that I understand.

$\endgroup$
  • $\begingroup$ $(1-1)^n$ develop this $\endgroup$ – Tsemo Aristide Jan 12 '16 at 2:34
  • 2
    $\begingroup$ @TsemoAristide That's not what's asked $\endgroup$ – leonbloy Jan 12 '16 at 2:44
7
$\begingroup$

You're alternating between even and odd terms. The proposition just says the sum of the even terms is the same as the sum of the odd terms. Combinatorially, that says that in a finite set, the number of subsets of even size equals the number of subsets of odd size. Here's a simple way to prove that.

Choose one of the $n$ elements to be the "distinguished" element. Every subset either contains the distinguished element or not. There is a one-to-one correspondence between those that contain the distinguished element and those that do not, thus: A set containing the distinguished element corresponds to a set containing exactly the same elements except that it does not contain the distinguished element. In every such pair of sets, one member of the pair has an even number of elements and the other has an odd number. Thus there are equally many of both. (In some cases the one with the distinguished element will be the one with an even number of elements and in some it will be the one with an odd number.)

$\endgroup$
  • $\begingroup$ This is very helpful, thank you for your response. I still need some time to ruminate on it, however. $\endgroup$ – user225477 Jan 12 '16 at 3:18
  • $\begingroup$ +1, if only for the absence of formulas in the answer. $\endgroup$ – Did Jan 25 '16 at 13:36
4
$\begingroup$

You get a bijection between the set of all even subsets of $[n]$ and all odd subsets by toggling whether 1 is an element.

$\endgroup$
2
$\begingroup$

The sum of the positive (resp. negative) terms count the total ways of selecting an even (resp. odd) number of elements from a total of $n$ elements. Let denote those counts by $e_n$ and $o_n$

Now, if $n$ is odd, it's easy to see that for each odd selection there is a corresponding even selection (take those elements that were left), so the counts are equal, $e_n=o_n$ and the net sum is zero.

If $n$ is even, it's a little trickier. Imagine we mark the first element. The even selections $e_n$ can be divided into those that include the first element (there are $o_{n-1}$) and those who don't (there are $e_{n-1}$). Then $e_n=e_{n-1}+o_{n-1}=o_n$

$\endgroup$
  • $\begingroup$ The second argument works regardless of whether $n$ is even or odd. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jan 12 '16 at 3:02
  • $\begingroup$ @MichaelHardy True. $\endgroup$ – leonbloy Jan 12 '16 at 3:28

Your Answer

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