Let the given statement be defined as
P(n): The number of subsets of a set containing n distinct
elements = 2n, for all n ϵ N.
Step1: For n = 1,
L.H.S=As, the subsets of the set containing only 1 element are:
Φ and the set itself
i.e. the number of subsets of a set containing only element = 2
R.H.S = 21 = 2
As, LHS=RHS, so, it is true for n=1.
Step2: Let the given statement be true for n = k.
P(k): The number of subsets of a set containing k distinct
elements = 2k
Now, we need to show P(k+1) is true whenever P(k) is true.
P(k+1):
Let A={a1, a2, a3, a4,…, ak , b} so that A has (k+1) elements.
So the subset t 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.
First collection: { }, {a1},{a1, a2},{a1, a2, a3},…,{a1, a2, a3, a4,…, ak} and
Second collection: {b}, {a1,b},{a1,a2,b },{a1,a2,a3,b},…,{a1,a2,a3,a4,…,ak , b}
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. {a1, a2, a3, a4,…, ak} = 2k
Also it follows that the second collection must have
the same number of the subsets as that of the first = 2k
So the total number of subsets of A = 2k+2k = 2k+1
Thus, by the principle of mathematical induction P(n) is true.