Browse by Stream
QnA
Home
QnA
Go To Your Study Dashboard

Get Answers to all your Questions

header-bg qa
  • Home
  • NCERT
  • Prove that number of subsets of a set containing n distinct elements is 2^n, for all n ϵ N.

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

 

Answers (1)

To Prove:

2^n is the no. of subsets of a set containing n distinct elements.

Now, there is only one subset since for a null set there is only one element φ

Now, we’ll substitute different values for n,

At n = 0,

No. of subsets = 1 = 2^0

If we consider a set that has 1 element then there will be 2 subsets that has 1 & φ

Thus, at n = 1, it is true

now at n=2 

No. of subsets = 2 = 2^2

Now, let us consider that there is a set S_k has k elements.

At n = k,

No. of subsets = 2^k is true.

Now, for set S_{k+1}, having k+1 elements,

Compared to the set S_{k}, S_{k+1} has an extra element and thus will form an extra collection of subsets when combined with the existing 2^k subsets & an extra 2^k subset will be formed.

Thus, at n = k+1,

No. of subsets = 2^k + 2^k

                        = 2.2^k

                        = 2^{k+1}

Thus, by mathematical Induction,

2^n is the no. of subsets of a set containing n distinct elements.

Posted by

infoexpert21

View full answer

Similar Questions

Latest Question