Department of Pre-University Education, KarnatakaPUC Karnataka Science Class 11

# 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 .

#### 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?

#### APPEARS IN

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