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

To prove; Number of subsets of a set containing n distinct elements is 2ⁿ.

For a null set there is only one element Φ and therefore only one subset.

⇒ at n = 0 number of subsets = 1 = 2⁰

By considering a set with 1 element there will be 2 subsets with 1 and Φ

⇒ at n = 0 number of subsets = 2 = 2²

By considering a set S_k with k element

Let at n = k number of subsets = 2^k be true.

For a set S_k+1 containing k+1 element

The extra one element in set S_k+1 when compared with S_k will form an extra collection of subsets by combing with the existing 2^k subsets and as a result an extra 2^k subsets are formed.

⇒ at n = k+1 number of subsets = 2^k + 2^k = 2.2^k = 2^k+1

⇒ P(k+1) is true.

∴ By Mathematical Induction number of subsets of a set containing n distinct elements is 2ⁿ, for all n ϵ N.