Prove that a set with n elements has 2n subsets.

From a set of elements, there is only one subset that can be chosen that contains no elements (the empty set), i.e. .

( denotes the binomial coefficient)

Similarly, there are possible subsets consisting of only one element that can be taken from the larger set, subsets consisting of two members, and so on, which means the total number of possible subsets that can be chosen is




Writing this as



we can apply the binomial theorem, which states that this is equivalent to .