Q. 455.0( 2 Votes )

# Prove that the number of subsets of a set containing n distinct elements is 2^{n} 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=2^{n}, 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^{1}=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_{1}, a_{2}, a_{3}, a_{4},…, 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_{1}},{a_{1}, a_{2}},{a_{1}, a_{2}, a_{3}},…,{a_{1}, a_{2}, a_{3}, a_{4},…, a_{k}} and

Second collection: {b}, {a_{1},b},{a_{1},a_{2},b },{a_{1},a_{2},a_{3},b},…,{a_{1},a_{2},a_{3},a_{4},…,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_{1}, a_{2}, a_{3}, a_{4},…, a_{k}}=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.

Rate this question :

Prove that cos α + cos (α + β) + cos (α + 2β) + … + cos (α + (n – 1)β) for all n ϵ N

RD Sharma - MathematicsProve that sin x + sin 3x + … + sin (2n – 1) x for all

nϵN.

RD Sharma - MathematicsProve the following by the principle of mathematical induction:

1.2 + 2.3 + 3.4 + … + n(n + 1)

RD Sharma - MathematicsProve the following by the principle of mathematical induction:

1.3 + 2.4 + 3.5 + … + n . (n + 2)

RD Sharma - MathematicsProve the following by the principle of mathematical induction:

RD Sharma - Mathematics

Prove the following by the principle of mathematical induction:

1^{2} + 3^{2} + 5^{2} + … + (2n – 1)^{2}

Prove the following by the principle of mathematical induction:

a + ar + ar^{2} + … + ar^{n – 1}

Prove the following by the principle of mathematical induction:

2 + 5 + 8 + 11 + … + (3n – 1) = 1/2 n(3n + 1)

RD Sharma - MathematicsProve the following by the principle of mathematical induction:

1.3 + 3.5 + 5.7 + … + (2n – 1) (2n + 1)

RD Sharma - MathematicsProve that for all natural

numbers, n ≥ 2.

RD Sharma - Mathematics