Prove that the number of subsets of a set containing *n* distinct elements is 2^{n}, for all *n *\[\in\] N .

#### Solution

\[\text{ Let the given statement be defined as } P\left( n \right): \text {The number of subsets of a set containing n distinct elements } = 2^n ,\text{ for all n } \in N . \]

\[\text{ Step I: For n } = 1, \]

\[\text { LHS = As, the subsets of a set containing only 1 element are: } \phi \text{ and the set itself } . \]

\[\text{ i . e . the number of subsets of a set containing only 1 element } = 2\]

\[\text{ RHS } = 2^1 = 2\]

\[\text{ As, LHS = RHS } \]

\[\text{ So, it is true for n } = 1 . \]

\[\text{ Step II: For n = k } , \]

\[\text{ Let } P\left( k \right): \text{ The number of subsets of a set containing k distinct elements } = 2^k , \text{ be true for some k } \in N . \]

\[\text{ Step III: For n } = k + 1, \]

\[P\left( k + 1 \right): \]

\[\text{ Let } A = \left\{ a_1 , a_2 , a_3 , . . . , a_k , b \right\} \text{ so that A has } \left( k + 1 \right) \text{ elements .} \]

\[\text{ So, the subset of A can be divided into two collections; first contains subsets of A which don't have b in them and } \]

\[ \text{ the second contains subsets of A which do have b in them } . \]

\[i . e . \]

\[\text{ First collection: } \left\{ \right\}, \left\{ a_1 \right\}, \left\{ a_1 , a_2 \right\}, \left\{ a_1 , a_2 , a_3 \right\}, . . . , \left\{ a_1 , a_2 , a_3 , . . . , a_k \right\} \text{ and } \]

\[\text { Second collection } : \left\{ b \right\}, \left\{ a_1 , b \right\}, \left\{ a_1 , a_2 , \right\}, \left\{ a_1 , a_2 , a_3 , b \right\}, . . . , \left\{ a_1 , a_2 , a_3 , . . . , a_k , b \right\}\]

\[\text{ It can be clearly seen that: } \]

\[\text{ The number of subsets of A in first collection = The number of subsets of set with k elements i . e } . \left\{ a_1 , a_2 , a_3 , . . . , a_k \right\} = 2^k \left( \text{ Using step II } \right)\]

\[\text{ Also, it follows that the second collection must have the same number of the subsets as that of the first } = 2^k \]

\[\text{ So, the total number of subsets of } A = 2^k + 2^k = 2 \times 2^k = 2^{k + 1} .\]

Hence, the number of subsets of a set containing *n* distinct elements is 2^{n }, for all *n* \[\in\] N .