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 question already has an answer here:

Suppose we have the following two identities:

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

The first says that the number of subsets of an $n$-set is $2^n$. The second says that the number of subsets of even size equals the number of subsets of odd size (of an $n$-set). Thus there are $2^{n-1}$ subsets of even length and $2^{n-1}$ subsets of odd length?

To combinatorially prove the second identity, let $A$ be a $k$-subset of $[n]$. Then note whether $k$ is odd or even?

share|improve this question

marked as duplicate by Grigory M, Daniel Rust, AlexR, Sasha, hardmath Jan 16 at 22:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
The first inequality is true for $n \geq 0$ while the second is true for $n \geq 1$ –  Martin Vatshelle Oct 15 '13 at 9:44

2 Answers 2

up vote 7 down vote accepted

The second identity can be proven by an inclusion-exclusion argument, but maybe it's clearer this way: pick an arbitrary element of the $n$-element set. Given a subset, if it contains the arbitrary element, remove it; otherwise, add it in. (That is, take the symmetric difference.) This defines a bijection from the set of subsets of odd size and the subsets of even size.

The generalization with $2$ replaced by a larger integer is less trivial; see this question.

As far as I can tell you are going through identities you know how to prove algebraically and trying to see how they can be proven combinatorially. If you are interested in learning how to do this systematically you should start with Benjamin and Quinn's Proofs that Really Count and then, if you are really serious, Bergeron, Labelle, and Leroux's Combinatorial Species and Tree-like Structures. There are also some blog posts and other material I could link you to if you want. Asking a question on this more general topic certainly seems more efficient than what you're currently doing.

share|improve this answer
    
Would you recommend the following: math.dartmouth.edu/archive/kpbogart/public_html/… –  PEV Dec 26 '10 at 23:24
    
@Trevor: it looks alright. –  Qiaochu Yuan Dec 26 '10 at 23:43

From another point of view you have:

$${\left( {1 + 1} \right)^n} =2^n= \sum\limits_{k = 0}^n {n \choose k}{{1^{n - k}}{1^k}}=\sum\limits_{k = 0}^n {n \choose k} $$

and

$${\left( {1 - 1} \right)^n} = 0 = \sum\limits_{k = 0}^n {n \choose k}{{1^{n - k}}{{\left( { - 1} \right)}^k}} = \sum\limits_{k = 0}^n {\left( { - 1} \right)}^k{n \choose k}$$

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.