Question

Prove the following theorem:

The total number of subsets of a finite set containing n elements is 2ⁿ.

Answer 1

To prove the above statement we have to use the combinations and binomial theorem. so first I will take an example then we can generalize it. Consider a set a containing 3 elements. A= {1,2,3}

First let's select 0 elements from 3 elements. That's no elements so that we will get the null set. No. of selection of 0 elements from 3 elements is 3C0 = 1

Then we select 1 element from 3.ie; {1},{2},{3} No. of selection of 1 element from 3 elements is 3C1=3

Select 2 elements from 2. i.e.; {1,2} {1,3} {2,3}. No. of selection of 2 elements from 3 elements is 3C2=3

Select 3 elements from three. i.e.; {1,2,3}. No. of selection of 3 elements from 3 elements is 3C3 = 1

So total no. of subsets of the above finite set is 3C+3C1+3C2+3C3 = 1+3+3+1 = 8 = 23

So when we generalize the case in the case of subset containing n elements the total no. of subsets is

nC0 + nC1 + nC2 + nC3 + nC4 + ..................... + nCn

In binomial theorem we have studied the expansion of (1+x )n = nC0 + nC1 x + nC2 x2 + nC3 x3 +nC4 x4 + .......... + nCn xn

Substitute 1 for x

So in the L.H.S we get (1+1)n = 2n

In R.H.S we get nC0+nC1+nC2 +nC3 +nC4 +..........+nCn

So nC0 + nC1 + nC2 + nC3 + nC4 + .......... + nCn = 2n

Hence the total no. of subsets of a finite set containing n elements is 2n