Question

Prove that the number of subsets of a set containing n distinct elements is $2^n$ for all $nϵN$.

Answer 1

Let P(n) : Number of subset fo a set containing n distinct elements is $2^n$, for all $nϵN$.

Step 1 we observe that P(1) is true, for n = 1

Number of subsets of a set contain 1 element is $2^1=2$, which is true.

Step II Assume that P(n) is true for n = k

P(k) : Number of subsets of a set containing k distinct elements is $2^k$, which is true.

Step III To prove P(k + 1) is true, we have to show that

P(k + 1) : Number of subsets of a set containing (k + 1) distinct elements is $2^{k+1}$. We know that, with the addition of one element in the set, the number of subsets become double.

$\therefore$ Number of subsets of a set containing (i + 1) distinct elements $=2\times 2^k=2^{k+1}$. So, P(k + 1) is true. Hence, P(n) is true.