5
$\begingroup$

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?

$\endgroup$

marked as duplicate by Grigory M, Dan Rust, AlexR, Sasha, hardmath Jan 16 '14 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.

  • $\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$

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.