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$
1
  • $\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$ May 1, 2016 at 0:43

2 Answers 2

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$
1
  • $\begingroup$ Ahh, thank you so much, but how did you come up with the approach? $\endgroup$
    – nyorkr23
    May 1, 2016 at 0:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .