Prove that the number of subsets of a set containing n distinct elements is 2

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

Step I: For $n=1$,

LHS $=$ As, the subsets of a set containing only 1 element are : $\phi$ and the set itself.

i. e. the number of subsets of a set containing only 1 element $=2$

RHS $=2^{1}=2$

As, LHS = RHS

So, it is true for $n=1$.

Step II : For $n=k$,

Let $\mathrm{P}(k)$ : The number of subsets of a set containing $k$ distinct elements $=2^{k}$, be true for some $k \in \mathbf{N}$.

Step III : For $n=k+1$,

$\mathrm{P}(k+1):$

Let $A=\left\{a_{1}, a_{2}, a_{3}, \ldots, a_{k}, b\right\}$ so that $A$ has $(k+1)$ elements.

So, the subset of $A$ can be divided into two collections; first contains subsets of $A$ which don't have $b$ in them and the second contains subsets of $A$ which do have $b$ in them.

i.e.

First collection: \{\}$,\left\{a_{1}\right\},\left\{a_{1}, a_{2}\right\},\left\{a_{1}, a_{2}, a_{3}\right\}, \ldots,\left\{a_{1}, a_{2}, a_{3}, \ldots, a_{k}\right\}$ and

Second collection: $\{b\},\left\{a_{1}, b\right\},\left\{a_{1}, a_{2},\right\},\left\{a_{1}, a_{2}, a_{3}, b\right\}, \ldots,\left\{a_{1}, a_{2}, a_{3}, \ldots, a_{k}, b\right$,

It can be clearly seen that:

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}, \ldots, a_{k}\right\}=2^{k}$(Using step II)

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

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 \mathbf{N}$.