Question

How can I prove that the number of proper subsets of a set with n elements is 2n−1 ?

Answer 1

The base case is n=0 . Such a set would be the empty set, which has zero proper subsets. Indeed, 20−1=0 , so the base case is proved.

 

Now suppose every set with k elements has 2k−1 proper subsets. We show that a set with (k+1) elements has 2k+1−1 proper subsets. Suppose the set in question is {a1,…,ak+1} . Take the subset {a1,…,ak} of k elements; this set must have 2k−1 proper subsets by the inductive hypothesis. Of course, these 2k−1 proper subsets are also proper subsets of the original set with (k+1) elements. Now, append each of these 2k−1 proper subsets with the element ak+1 — these further 2k−1 sets are also proper subsets of {a1,…,ak+1} . The only proper subset of {a1,…,ak+1} left that is neither among the former 2k−1 nor among the latter 2k−1 is the set {a1,…,ak} . Thus, the set {a1,…,ak+1} has (2k−1)+(2k−1)+1 proper subsets, which is equal to 2(2k−1)+1=2k+1−2+1=2k+1−1 .

The induction is complete.

 

 

Given above