Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $S$ be a subset of $\mathbb{N}$ such that $$2^k\in S\quad\forall\ k\in\mathbb N$$ and, $$k\in S\Rightarrow k-1\in S\quad\forall\ k\ge2,k\in\mathbb N$$

Show by induction that $S=\mathbb N$.

share|improve this question
    
$\mathbb{N}=\{1,2,3,4,\cdots\}$ –  Spenser Sep 3 '12 at 16:08
    
The second property says "If something is in $S$, then everything below it is, as well", while the first property gives you a way of finding an arbitrarily large element of $S$, albeit in a particular way (with powers of $2$). –  Kirk Boyer Sep 3 '12 at 20:02
1  
Related: math.stackexchange.com/questions/27328/… –  JavaMan Oct 14 '12 at 5:31

4 Answers 4

up vote 8 down vote accepted

Hint $\ $ If one views this as a sort of interval (or segment) induction, then it becomes obvious, namely $\Bbb N$ is the only unbounded initial segment of $\Bbb N.$ Below is the simple proof.

Lemma $\rm\ S\subset \mathbb N\:$ satisfies $\rm\:n+1\in S\:\!\Rightarrow n \in S\,\ $ iff $\rm\,\ S\:$ is an initial segment of $\:\mathbb N$

Proof $ $ (hint) $ $ If $\rm\:S\ne \mathbb N\:$ then $\rm\:S = [0,m)\:$ for the least $\rm\:m\not\in S,\:$ since by induction, nonmembership ascends from $\rm\:m\:$ by $\rm\:n\not\in S\:\Rightarrow\:n+1\not\in S\:$ (contrapositive of the hypothesis).

Corollary $ $ If, additionally, $\rm\:S\:$ is unbounded then $\rm\:S = \mathbb N$

In your case, $\rm\,S\,$ is an initial segment by your second hypothesis and the Lemma, and $\rm\: S\ne \{\ \}\:$ is unbounded via the hypothesis $\rm\:n\in \Bbb N\:\Rightarrow\:2^n\in S.$ Therefore, by the corollary, $\rm\, S = \Bbb N.$

Notice how abstracting the matter set-theoretically helps to make clearer the key structure.

See also this closely related question, where it is referred to as Cauchy's method of induction. Sometimes it is called back-and-forth induction. It occurs frequently in competition problems.

share|improve this answer

$$(1)\,\,2^1=2\in S\Longrightarrow 2-1=1\in S$$ $$(2)\,\,\text{Suppose }\,\,m\in S\,\,,\,\forall\, m<n$$ Let now $\,t\in\Bbb N\,$ be s.t. $\,2^{t-1}<n\leq 2^t\,$ : $$2^t\in S\Longrightarrow 2^t-1\in S\Longrightarrow 2^t-1-1=2^t-2\in S,...$$ After no more than $\,2^{t-1}\,$ steps as above, we'll reach $\,2^t-h=n\in S\,,\,0\leq h<2^{t-1}\,$ , and we're done.

Now brush this up a little and formalize.

share|improve this answer

Here is a somewhat bizarre application of mathematical induction.

Let $T$ be a subset of $\Bbb{N}$ consisting of positive integers $k$ satisfying the following proposition:

Whenever $U \subset \Bbb{N}$ satisfies

  • (Property $A_k$) $2^k \in U$ and
  • (Property $B$) $l \in U$ and $l \geq 2$ implies $l-1 \in U$,

we must have $\{ 1, \cdots, 2^k \} \subset U$.

We claim that $T = \Bbb{N}$ by induction.

1. It is easy to check that $1 \in T$.

2. Assume $k \in T$. Let $U \subset \mathbb{N}$ satisfies the property $A_{k+1}$ and $B$. Let $$U' = \{l \in \Bbb{N} : l+2^k \in U \}.$$ Then

  • $2^k \in U'$ and hence $U'$ satisfies $A_k$.
  • Also, if $l \in U'$ and $l \geq 2$, then $B$ implies that $l+2^k-1 \in U$. Since $l-1 \geq 1$, this implies $l-1 \in U'$. Thus $U'$ also satisfies $B$.

Now induction hypothesis shows that $\{1, \cdots, 2^k \} \subset U'$, or equivalently, $\{2^k + 1, \cdots, 2^{k+1}\} \subset U$. Then $B$ implies $2^k \in U$, or in other words, $A_k$. Thus by induction hypothesis again, $\{1, \cdots, 2^k \} \subset U$. Therefore $k+1 \in T$.

Thus by mathematical induction, $T = \Bbb{N}$.

Finally, let $n \in \mathbb{N}$. Then $n \leq 2^n$, and $S$ satisfies both the property $A_n$ and $B$. Therefore $n \in \{ 1, \cdots, 2^n \} \subset S$ and hence $\mathbb{N} = S$.

share|improve this answer

Hint: First show that if $n\in S$, then $\{1,2,\dots, n\} \subseteq S$. You do this by induction. So the "base" or the start is to note that $n\in S$. Then the "bridge" or the induction step is to note that $k\in A \Rightarrow k-1\in S$. Hence $\{1,2,\dots, n\} \subseteq S$.

Continue: You know that $S\subseteq \mathbb{N}$. So you need just show that all natural numbers are elements of $S$. Let $n\in \mathbb{N}$. You need to show that this randomly given number is in $S$. Now $\lim_{k\to \infty} 2^k = \infty$, so there is a $k\in \mathbb{N}$ such that $2^k > n$. Now for that $k$, $2^k \in S$. So $$ n = 2^k - (2^k - n) \in S. $$

share|improve this answer
    
Can you clarify what is the base and the bridge of the induction? –  Spenser Sep 3 '12 at 16:30
    
Ok, I will edit –  Thomas Sep 3 '12 at 16:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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