Problem 1. Recall from Week 2 that the number of subsets of a set of n elements

Question

Problem 1. Recall from Week 2 that the number of subsets of a set of n elements is 2n. We saw that this follows from the Multiplication Principle.

Now, prove this statement using Mathematical Induction.

Hint for the inductive step: Let X be a non-empty set. Let a be some specific element of X. Then the subsets of X can be divided into two types: Those that contain a and those that do not.

Explanation / Answer

The number of subsets of a set of n elements is 2^n take an elemet "a" from the set let n=1 number of subsets=number of subsets containing a+number of subsets not containing a =>1+1=2^1 ==>2=2 let us assume from n=k its true number of subsets of a set of k elements is 2^k now fro n=k+1 means one extra element is added we can have mare 2^k subsets containing that element. total subsets=2^k(not containing extra element) +2^k(containing extra element) =2(2^k) =2^(k+1) hence proved

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.