Number of even and odd subsets [duplicate]

Solution 1:

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.

Solution 2:

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