Prove that the number of subsets of a set containing n distinctelements is 2n for all n ϵ N.
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.