please give complete justification for each of the assertion

please give complete justification for each of the assertions in the proof

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 2^m subsets. Prove the observation, i.e., that, {1, 2, 3,...,k, k, + 1} has double the number of subsets of {1, 2, 3...,k}.

Solution

2)

a) Base Case (n=0 & n=1)

If the set contains 0 elements, then the number of subsets will be 1, which contains the element phi or the null set

For n=1, there will be 2 subsets which are phi and the element itself

Assumption: Let us assume that the number of subsets of the group containing k elements is equal to 2^k

Inductive Step: Since the k elements can form 2^k subsets, then the (k+1)th element will either belong to each of those formed sets or will not belong to those sets

Hence number of sets = 2^k (sets not containing the (k+1)th element) + 2^k (sets containing the (k+1)th element)

=> 2^(k+1)

Hence by mathematical induction, we can show that the number of subsets of n-element group is 2^n

Now for the first part

Number of subset for k elements set = 2^k

Number of subsets for (k+1) elements set = 2^(k+1)

Ratio of both the quantities is equal to 2^(k+1)/2^k = 2