InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
What is the total number of proper subsets of a set containing n elements? |
|
Answer» Let P(n) : number of subset of a set containing n distinct elements `2^(n)`, for all n `in N`. Step I We observe that of P(1) is true, for n=1. Number of subsets of a set contain 1 element is `2^(1)=2`, which is true. Step II Assume that P(n) is true for n=k. P(k) : Number of subsets of a set containing k distinct elements is `2^(k)`, which is true. Step III To prove P(k+1) is true, we have to show that P(k+1): Number of subsets of a set containing (k+1) distinct elements is `2^(k+1)` We know that, with addition of one element in the set number of subsets become double. `:.` Number of subsets of a set containing (k+1) distinct elements `=2xx2^(k)=2^(k+1)`. So, P(k+1) is true. Hence, P(n) is true. |
|