Homework SourseHow many subsets does the set 1 2 n have Prove your answer
How many subsets does the set {1, 2, ..., n} have? Prove your answer using the Product Rule.
Solution
Let A={1,2,....,n}
n(A)= n
Subsets of A can be of size 0,1,2,...,n.
A subset of size r (r=0,1,2,...,n) can be formed by selecting any r elements from the n elements of A.
Hence no. of subsets of size r is equal to the no. of ways one can select r elements from n elements, which can be done in nCr ways.
Hence total no. of subsets of any size = nC0 +nC1 + nC2 +.......+nCn = 2n (by binomial theorem)
