2
$\begingroup$

I know the steps to an induction proof. The first step is to establish that $n=1$ is true. Then the second step is to assume that if we replaced $n$ by $k$, $2^k$ is true. For the third step, assuming the assumption is true, prove that $2^{k+1}$ is true. Well, the problem is, what do I set $2^k$ equal to and what do I set $2^{k+1}$ equal to?

$\endgroup$
  • $\begingroup$ First of all, you don't prove that "$2^n$" is true. You prove that "The number of subsets of a set that has $n$ elements is $2^n$" is true. ... This means if you assume that the number of subsets of an $k$-element set is $2^k$, you need to show that the number of subsets of a $(k+1)$-element set is $2^{k+1}$. $\endgroup$ – Christopher Carl Heckman May 1 '16 at 0:43
3
$\begingroup$

If $n=k$ is true, then there are $2^k$ subsets $X_i$ of {$1,2,...,k$}.

Now any subset of {$1,2,...,k,k+1$} either does not contain $k+1$, and therefore is one of the $X_i$ from above, or it does contain $k+1$, in which case it is of the form $X_i$ U {$k+1$}, so there are $2^k+2^k=2^{k+1}$ subsets

$\endgroup$
3
$\begingroup$

Hint: Let $S_{k + 1} = \{s_1, \ldots, s_k, s_{k + 1}\}$ be our set of $k + 1$ elements. We want to show that $S_{k + 1}$ has exactly $2^{k + 1}$ subsets. Indeed, notice that any subset $T$ of $S_{k + 1}$ falls under $1$ of $2$ cases:

  • Case 1: Suppose that $s_{k + 1} \in T$. Then we can rewrite $T$ in the form $T = T' \cup \{s_{k + 1}\}$, where $T'$ is any subset of $S_k = \{s_1, \ldots, s_k\}$. But hey, now we can apply the induction hypothesis!

  • Case 2: Suppose that $s_{k + 1} \notin T$. Then $T$ is actually a subset of $S_k = \{s_1, \ldots, s_k\}$. But hey, now we can apply the induction hypothesis!

Conclude by adding up the number of subsets from Case 1 and Case 2.

Spoiler alert: You should get $2^{k + 1}$.

$\endgroup$
  • $\begingroup$ Ahh, thank you so much, but how did you come up with the approach? $\endgroup$ – nyorkr23 May 1 '16 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.