Question

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

Answer 1

Let the given statement be defined as 

P(n): The number of subsets of a set containing n distinct 

elements = 2ⁿ, 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 = 2¹ = 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 = 2^k 

Now, we need to show P(k+1) is true whenever P(k) is true. 

P(k+1): 

Let A={a₁, a₂, a₃, a₄,…, a_k , 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: { }, {a₁},{a₁, a₂},{a₁, a₂, a₃},…,{a₁, a₂, a₃, a₄,…, a_k} and 

Second collection: {b}, {a₁,b},{a₁,a₂,b },{a₁,a₂,a₃,b},…,{a₁,a₂,a₃,a₄,…,a_k , 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. {a₁, a₂, a₃, a₄,…, ak} = 2^k 

Also it follows that the second collection must have 

the same number of the subsets as that of the first = 2^k 

So the total number of subsets of A = 2^k+2^k = 2^k+1 

Thus, by the principle of mathematical induction P(n) is true.