# Prove that the number of subsets of a set containing n distinct elements 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.

Rate this question :

How useful is this solution?
We strive to provide quality solutions. Please rate us to serve you better.
Related Videos  Take the challenge, Quiz on Vectors37 mins  Vectors- Cosine & SIne Rule54 mins  Addition of Vectors - Kick start Your Preparations47 mins  Scalar and Vector Product49 mins  Interactive Quiz on vector addition and multiplications38 mins  Revise Complete Vectors & it's application in 50 Minutes51 mins  Scalar and vector product in one shot56 mins  Quick Revision of Vector Addition and Multiplications37 mins  Quiz | Vector Addition and Multiplications35 mins  Unit Vectors24 mins
Try our Mini CourseMaster Important Topics in 7 DaysLearn from IITians, NITians, Doctors & Academic Experts
Dedicated counsellor for each student
24X7 Doubt Resolution
Daily Report Card
Detailed Performance Evaluation view all courses 