Prove by induction that the number of subsets of an n-element set is 2^n for n ≧ 0.1. Base case2. Inductive hypothesis3. What we have to show4. ProofA set with no elements is the empty set. The...

Prove by induction that the number of subsets of an n-element set is 2^n for n ≧ 0.
1. Base case
2. Inductive hypothesis
3. What we have to show
4. Proof

A set with no elements is the empty set. The set of all subsets of an n-element set includes the empty set.

I want to know the base case, state the inductive hypothesis, state what we have to show, and proof proper for this question. 

Asked on by araion

1 Answer | Add Yours

Top Answer

mlehuzzah's profile pic

mlehuzzah | Student, Graduate | (Level 1) Associate Educator

Posted on

Base case: n=0

The only set containing 0 elements is the empty set. The only subset of the empty set is the empty set. Thus the number of subsets of a 0-element set is 1, which is `2^0`

 

Inductive hypothesis:

Suppose that the number of subsets of a k-element set is `2^k`

Then we want to show that the number of of subsets of a (k+1)-element set is `2^(k+1)`

So suppose we have a (k+1)-element set B. We can write B as: `B=A uu {a}` where `a` is one of the elements of B, and all the rest of the elements comprise the set `A`. So `A` is a k-element set. By our induction hypothesis, there are `2^k` subsets of A. Now, we want to count the number of subsets of B. To do that, we start with a subset of A, and then decide whether or not we want to add `a` to our subset of B. Thus, for each subset of A there are two possible subsets of B; they are: `A` and `A uu {a} ` So there are `(2)*(2^k)=2^(k+1)` subsets of B.


We wanted to assume that the number of subsets of a k-element set is `2^k` and use that to prove that the number of subsets of a (k+1)-element set is `2^(k+1)`. So we are done.

We’ve answered 318,989 questions. We can answer yours, too.

Ask a question