2 a Using the observation that for all positive integers k 1

2. (a) Using the observation, that, for all positive integers k, {1, 2, 3, ......k, k + 1} has double the number of subsets of {1, 2, 3 ....... k}, use Mathematical Induction to prove that {1, 2, 3,...... n} has 2n subsets. (b) Prove the observation, i.e., that,{1, 2, 3, ......k, k + 1} has double the number of subsets of {1, 2, 3 ....... k}, Hint: Consider the subsets of,{1, 2, 3, ......k, k + 1} which contain k + 1. Show that they are in one-to-one correspondence with those which do not contain k + 1.

Solution

a) Base Case(n=0)

The element with 0 elements contains only 1 subset which is phi or null element, {phi}

RHS = 2^0 = 1

Hence the base case is satisfied

Inductive Step(n=k)

Let us assume that the given thing is true for (n=k)

Number of subsets will be 2^k

Hypothesis step (n=k+1)

Since the number of subsets with k elements is equal to 2^k

The addition of (k+1) element can be done to either these 2^k subsets or not

2^k(if (k+1)the element is added to the subset) + 2^k (if (k+1)th element is not added)

=> 2 . 2^k

=> 2^(k+1)

Hence the number of subsets will be equal to 2^(k+1)

Therefore by using the principle of mathematical induction we can say that prove that {1, 2, 3,...... n} has 2n subsets.