Question

Prove that number of subsets of a set containing n distinct elements is 2ⁿ, for all n ∈ N.

Answer 1

Let P(n) : Number of subsets of a set containing n distinct elements is 2ⁿ, ∀ n ∈ N

Step 1: It is clear that P(1) is true for n = 1.

Number of subsets = 2¹ = 2.

Which is true.

Step 2: P(k) is assumed to be true for n = k.

Since the number of subsets = 2^k.

Step 3: P(k + 1) = 2^{k + 1}

We know that if one number (i.e., element) is added to the elements of a given set, the number of subsets become double.

∴ Number of subsets of set having (k + 1) distinct elements = 2 × 2^k = 2^{k + 1}

Which is true for P(k + 1).

Hence P(k + 1) is true whenever P(k) is true.