Q. 455.0( 2 Votes )

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

Answer :

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 VectorsTake the challenge, Quiz on VectorsTake the challenge, Quiz on Vectors37 mins
Vectors- Cosine & SIne RuleVectors- Cosine & SIne RuleVectors- Cosine & SIne Rule54 mins
Addition of Vectors - Kick start Your PreparationsAddition of Vectors - Kick start Your PreparationsAddition of Vectors - Kick start Your Preparations47 mins
Scalar and Vector ProductScalar and Vector ProductScalar and Vector Product49 mins
Interactive Quiz on vector addition and multiplicationsInteractive Quiz on vector addition and multiplicationsInteractive Quiz on vector addition and multiplications38 mins
Revise Complete Vectors & it's application in 50 MinutesRevise Complete Vectors & it's application in 50 MinutesRevise Complete Vectors & it's application in 50 Minutes51 mins
Scalar and vector product in one shotScalar and vector product in one shotScalar and vector product in one shot56 mins
Quick Revision of Vector Addition and MultiplicationsQuick Revision of Vector Addition and MultiplicationsQuick Revision of Vector Addition and Multiplications37 mins
Quiz | Vector Addition and MultiplicationsQuiz | Vector Addition and MultiplicationsQuiz | Vector Addition and Multiplications35 mins
Unit VectorsUnit VectorsUnit 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
caricature
view all courses