5
$\begingroup$

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?

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

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.

$\endgroup$
3
  • $\begingroup$ Would you recommend the following: math.dartmouth.edu/archive/kpbogart/public_html/… $\endgroup$ – PrimeNumber Dec 26 '10 at 23:24
  • $\begingroup$ @Trevor: it looks alright. $\endgroup$ – Qiaochu Yuan Dec 26 '10 at 23:43
  • $\begingroup$ @ Qiaochu Yuan,on what inclusion-exclusion principle is needed to be used ? $\endgroup$ – user771003 May 22 '20 at 8:16
3
$\begingroup$

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}$$

$\endgroup$

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