Department of Pre-University Education, KarnatakaPUC Karnataka Science Class 11
Advertisement Remove all ads

Prove that the Number of Subsets of a Set Containing N Distinct Elements is 2n, for All N ∈ N . - Mathematics

Prove that the number of subsets of a set containing n distinct elements is 2n, for all n \[\in\] N .

 
Advertisement Remove all ads

Solution

\[\text{ Let the given statement be defined as }  P\left( n \right): \text {The number of subsets of a set containing n distinct elements }  = 2^n ,\text{  for all n }  \in N . \]

\[\text{ Step I: For n  } = 1, \]

\[\text { LHS = As, the subsets of a set containing only 1 element are: } \phi \text{ and the set itself } . \]

\[\text{ i . e . the number of subsets of a set containing only 1 element } = 2\]

\[\text{ RHS }  = 2^1 = 2\]

\[\text{ As, LHS = RHS } \]

\[\text{ So, it is true for n } = 1 . \]

\[\text{ Step II: For n = k } , \]

\[\text{ Let } P\left( k \right): \text{ The number of subsets of a set containing k distinct elements } = 2^k , \text{ be true for some k }  \in N . \]

\[\text{ Step III: For n } = k + 1, \]

\[P\left( k + 1 \right): \]

\[\text{ Let } A = \left\{ a_1 , a_2 , a_3 , . . . , a_k , b \right\} \text{ so that A has } \left( k + 1 \right) \text{ elements .}  \]

\[\text{ So, the subset of A can be divided into two collections; first contains subsets of A which don't have b in them and } \]

\[ \text{ the second contains subsets of A which do have b in them } . \]

\[i . e . \]

\[\text{ First collection: }  \left\{ \right\}, \left\{ a_1 \right\}, \left\{ a_1 , a_2 \right\}, \left\{ a_1 , a_2 , a_3 \right\}, . . . , \left\{ a_1 , a_2 , a_3 , . . . , a_k \right\} \text{ and } \]

\[\text { Second collection } : \left\{ b \right\}, \left\{ a_1 , b \right\}, \left\{ a_1 , a_2 , \right\}, \left\{ a_1 , a_2 , a_3 , b \right\}, . . . , \left\{ a_1 , a_2 , a_3 , . . . , a_k , b \right\}\]

\[\text{ It can be clearly seen that:  } \]

\[\text{ The number of subsets of A in first collection = The number of subsets of set with k elements i . e } . \left\{ a_1 , a_2 , a_3 , . . . , a_k \right\} = 2^k \left( \text{ Using step II } \right)\]

\[\text{ Also, it follows that the second collection must have the same number of the subsets as that of the first } = 2^k \]

\[\text{ So, the total number of subsets of  } A = 2^k + 2^k = 2 \times 2^k = 2^{k + 1} .\]

Hence, the number of subsets of a set containing n distinct elements is 2n , for all n \[\in\] N .

 
  Is there an error in this question or solution?
Advertisement Remove all ads

APPEARS IN

RD Sharma Class 11 Mathematics Textbook
Chapter 12 Mathematical Induction
Exercise 12.2 | Q 45 | Page 29
Advertisement Remove all ads

Video TutorialsVIEW ALL [1]

Advertisement Remove all ads
Share
Notifications

View all notifications


      Forgot password?
View in app×