To prove; Number of subsets of a set containing n distinct elements is 2n.
For a null set there is only one element Φ and therefore only one subset.
⇒ at n = 0 number of subsets = 1 = 20
By considering a set with 1 element there will be 2 subsets with 1 and Φ
⇒ at n = 0 number of subsets = 2 = 22
By considering a set Sk with k element
Let at n = k number of subsets = 2k be true.
For a set Sk+1 containing k+1 element
The extra one element in set Sk+1 when compared with Sk will form an extra collection of subsets by combing with the existing 2k subsets and as a result an extra 2k subsets are formed.
⇒ at n = k+1 number of subsets = 2k + 2k = 2.2k = 2k+1
⇒ P(k+1) is true.
∴ By Mathematical Induction number of subsets of a set containing n distinct elements is 2n, for all n ϵ N.