Help with Induction q (1 Viewer)
- Thread starter z3bra
- Start date
Which question? I'll assume Q.12. For the induction step, assume that a k-set (i.e. a k-member set) has 2^k subsets for some particular non-negative integer k. Consider putting in one more element now (call it X) to have a (k+1)-set. What are the subsets of these? Well there are all the 2^k subsets from the original k-set. But those are the precisely all the subsets that don't contain X. The other subsets are the ones that do contain X. How many such subsets are there? Well if we have X, we can choose to put in extra elements from the remaining k members of the set to form the subset with X in it, and the no. of ways to do this is just equal to the no. of subsets of a k-set (because when we put extra members in, these extra members inputted are forming a subset of the original k-set). Thus there are 2^k subsets that contain X.
Could someone please show me the working for this question. I don't really understand it.
Sent from my iPhone using Tapatalk
So as we said, there are 2^k subsets that don't contain X, and there are 2^k subsets that do contain X. So the total no. of subsets of the (k+1)-set is (2^k) + (2^k) = 2^(k+1), which completes the induction step.