A Set of Cardinality n has 2^n subsets

This is the easiest way I know how to do it.

Let S be a set with cardinality n.

Recall that nCk is the number of k-element subsets of an n-element set.

Then to find the total number of subsets, we can just literally add them all up.

So we will add up,
All 0-element subsets, there are nC0 of these.
All 1-element subsets, there are nC1 of these.
All 2-element subsets, there are nC2 of these.
All 3-element subsets, there are nC3 of these.
.
.
.
All n-1-element subsets, there are nCn-1 of these.
All n element subsets, there are nCn of these.

So we have,

total number of subsets = nC0 + nC1 + nC2 + nC3 + ... + nCn-1 + nCn

On the other hand, via the binomial theorem we have,
2^n = (1 + 1)^n = SUM(nCk1^k 1^(n-k)) = nC0 + nC1 + nC2 + nC3 + ... + nCn-1 + nCn.

Done!