Question

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

Answer 1

There are
`\dbinomk` 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|)\binomk`

Recalling the binomial theorem, the above sum is equal to

`\displaystyle\sum_(k=0)^(|A|)\binomk1^k1^(|A|-k)=(1+1)^(|A|)=2^(|A|)`

as required.