Question

Prove that if a set S has n elements, then S has 2^n subsets.

Answer 1

You can do it by induction. Suppose a set of N elements has 2^N subsets. Then add an N+1st element. Then you can create 2^N new subsets from the original subsets, by adding that N+1st element to each of them, plus you have the original 2^N, for a grand total of 2^N+2^N = 2^(N+1).

There's a simpler argument, though, that just says: for each element and each subset, that element either is or isn't in the subset: two options. So the total number of subsets is 2^N.