Question

Give a combinatorial proof that the cardinality of the power set of a finite set A is 2^|A|

Answer 1

There are $\dbinom{|A|}k$ ways of building a subset of $k$ elements from $A$, so the total number of subsets you can build is

$\displaystyle\sum_{k=0}^{|A|}\binom{|A|}k$

Recalling the binomial theorem, the above sum is equal to

$\displaystyle\sum_{k=0}^{|A|}\binom{|A|}k1^k1^{|A|-k}=(1+1)^{|A|}=2^{|A|}$

as required.