1
$\begingroup$

Let $S\subseteq \mathbb{N}$ where: (i) $2^k\in S$ for all $k\in \mathbb{N}$; and (ii) for all $k\ge 2$, if $k\in S$, then $k-1\in S$. Prove using induction that $S=\mathbb{N}$.

So the base case: If $k=1$, then by (i) $2^1=2\in S$. Then by (ii), $1\in S$.

Now the assumption, $k\le n$. So we assume that for all $k\le n$ that through (i) we have $2^k\in S$. But now that we know that by (ii) $2^k\in S$, so therefore $2^k-1, 2^k-2,...,2^{k-1}+1$ are all in $S$. (Seems like a kind of reverse induction?...) So now I think all integers up to $2^k$ are assumed to be in $S$

So finally, for $2^{k+1}$, we have that $2^{k+1}\in S$. But since $2^{k+1}\in S$, so is $2^{k+1}-1$ by (ii) and thus so is $2^{k+1}-2, 2^{k+1}-3,...,2^{k+1}-(2^k-1)$. This last value is nothing more than

$$2^{k+1}-(2^k-1)=2^{k+1}-2^k+1=2^{k}(2-1)+1=2^k+1$$

And since we know $2^k\in S$ then every integer in between $2^k$ and $2^{k+1}$ is now also in $S$. Thus, for all natural numbers $k$, all integers are in $S$ which means finally that $S=\mathbb{N}$.

I've never done an induction proof like this before, so I was challenging myself to understand the logic of why it to be true and I think I succeeded, but there's a nagging feeling that I'm not using my assumptions in the correct manner, so I'm thinking that this line of reasoning and logic is wrong. Can anyone please take a look and see if I'm right or my logic is faulty?

$\endgroup$
  • 1
    $\begingroup$ in the base case, you say that by (i) $2^1 = 2 \in S$, but by the (i), you can only afirm that if $1 \in S$ $\endgroup$ – Ulivai May 22 at 19:16
  • $\begingroup$ I'm not getting what your saying. Since by (i), 2 is now in the set, then by (ii), since 2 is now in S, 1 must also now be in S. That's how I read it. $\endgroup$ – Mando May 22 at 19:19
  • 1
    $\begingroup$ +1 I think the title was pretty good! I added “Proof verification” (because it reflects that you did put in the work, nice job) and the proof-verification which displays solution-verification as a synonym instead for some reason. $\endgroup$ – gen-z ready to perish May 22 at 19:29
  • 1
    $\begingroup$ @Mando I deleted my comment because it was based on your original question text stating $k \in S$ which you had not corrected. The problem with that condition is that you're not actually guaranteed a base case to induce from. You must have a stipulation that at least one natural number greater than or equal to $2$ belongs to $S$, in which case the question is doable even with the condition written as $k\in S$. $\endgroup$ – Deepak May 22 at 19:34
  • 1
    $\begingroup$ @Mando Your base case should actually be $2$. Applying (ii) to $k=2$ will reveal that $1\in S$. Pretty sneaky, huh.... $\endgroup$ – gen-z ready to perish May 22 at 19:47
1
$\begingroup$

In the base case, you say: “Then by (ii), $1\in S$.” Unfortunately, (ii) only applies to $k\ge2$.

The base case should actually be two steps, as follows. Take $k_{\rm (i)}=1$, so (i) guarantees $2\in S$. Now take $k_{\rm (ii)}=2$, so (ii) guarantees $2-1=1\in S$.

Now proceed! You have a good handle on how induction works; the rest is perfect.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Step back and ask..... what's going on?

For any $n\in \mathbb N$ we can find $k$ so that $2^k \ge n$. And $2^k \in S$ so because $n \le 2^k$ then $n\in S$. So every $n\in N$. And so $\mathbb N \subset S \subset \mathbb N$ so $S = \mathbb N$.

Sure that seems simple enough.

But we must prove two things:

1) For any $n\in \mathbb N$ we can find $k$ so that $2^k \ge n$

2) If $k\in S$ and $n\le k$ then $n \in S$.

I'd actually do this in two separate proofs.

And for each proof be induction the key will be forming the statement.

Proof 1: $P(n):=$ for any $n$ there is a $k$ so that $2^k \ge n$.

Base case: $n = 1$ if $n=1$ then $k=1$ and $1 < 2^1$.

Induction step: $n=m$, assume there is some $k_m$ so that $m \le 2^{k_m}$.

If $m < 2^{k_m}$ then $m + 1 \le 2^{k_m}$.

(That's clear, right? If $a,b \in \mathbb Z$ then $a < b\implies a+1 \le b$.... we don't need to prove that do we? We can... $b-a \in \mathbb Z$ and $b-a> 0$ so $b-a\ge 1$ so $a+1 \le b$.)

And if $m = 2^{k_m} \ge 1$ then $m+1 \le m + m = 2m =2*2^{k_m}=2^{k_m + 1}$.

That's it. Proof 1: is done.

Proof 2: You noted you did a sort of "backwards induction". But note, if you make your $Q(n)$ statement right is is a forward induction.

Fix $k$ as a constant so that $k\in S$.

$Q(n):= $ $k-n\in S$ for all $n= 0,......, k$.

Base case: $n=0$; Then $k - 0=k-1\in S$.

Induction step: $n=m$ and assume $k-m \in S$. If $k-m \ge 2$ then $k-(m+1) = (k-m)-1 \in S$. And if $k-m< 2$ but $k-m \in \mathbb N$ then $m = k-1$ and we've gone as for as we need.

......

By the way.....

The is a property very similar to a "backwards proof by induction using contradiction" using the well ordered principal of natural number.

WOP: Every non-empty subset of natural numbers has a least,first element.

So if you are ask to prove $P(n)$ is true for all natural $n$ you can do this:

Show $P(1)$ is true.

Consider the set of all natural numbers where $P(n)$ is FALSE. Assume it is not empty.

Let $k$ be the least element; that is $k$ is first case where $P(k)$ is false.

Prove $P(k)$ is false $\implies P(k-1)$ is false.

But that's a contradiction because $k$ was the first such number so $P(k-1)$ can't be false.

So the set of natural numbers where $P(n)$ is false is empty.

So $P(n)$ is always true.

.....

If if $P(n)$ is $n \in S$. then

Well $2^1 \in S$ so $2-1= 1$ is in $S$ so $P(1)$ is true.

Let $m$ be the first natural number where $m \ne \in S$.

Then $m = (m+1)-1$ so $m+1\in S\implies m\in S$. So $m+1\not\in S$. And so by induction for all $k > m$ then $k \not\in S$.

Now $2^m > m$. So $2^m\not \in S$. But that's a contradiction.

SO there is no natural number not in $S$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. This is good. I am unpacking it a bit for the minutiae but I follow the logic. $\endgroup$ – Mando May 22 at 19:58
  • $\begingroup$ I awarded the answer to someone else, not because I thoughtyou were wrong but because the person was helping me throughout the comment thread. I appreciate all of your proofs and help because it definitelty helped me understand the problem as a whole, not just to fix my understanding/misunderstanding. Thank you so much. $\endgroup$ – Mando May 22 at 20:18
  • $\begingroup$ What is “backwards proof by induction using contradiction”? $\endgroup$ – gen-z ready to perish May 22 at 21:26
  • $\begingroup$ "What is “backwards proof by induction using contradiction”?" It's proof by induction that goes backward and uses a contradiction, much as that example does. $\endgroup$ – fleablood May 22 at 21:54
1
$\begingroup$

Let $T$ be a subset of $\Bbb N$ with the following properties:

  • There exists some $t_0\in T$ with $t_0>1$
  • If $t\in T$, then there exists $m\in \Bbb N$ with $t+m\in T$

Example. The set of powers of two has this property: Just let $t_0=2$, and for $t=2^k\in T$, we can let $m=t$ and have $m+t=2t=2^{k+1}\in T$.

Let $S$ be a subset of $\Bbb N$ with $T\subseteq N$ and if $s\in S$ with $s>1$ then $s-1\in S$.

Lemma 1. $\forall k\in\Bbb N\colon \forall n\in\Bbb N\colon n+k\in T\to n\in S.$

Proof. [Induction on $k$] For $k=1$, $n+1\in T\subseteq S$ implies $n\in S$, as desired.

For $k>1$, $k=1+k'$, assume $$\tag1\forall n\in\Bbb N\colon n +k'\in T\to n\in S.$$ Let $n\in \Bbb N$ with $n+k\in T$. Then $n+k=(n+1)+k'$, so by $(1)$, $n+1\in S$ and hence also $n\in S$. Hence $\forall n\colon n+k\in T\to n\in S$.

Now the lemma follows by induction. $\square$

Lemma 2. $ \forall n\in\Bbb N\colon \exists k\in\Bbb N\colon n+k\in T.$

Proof. For $n=1$ we can take $k=t_0-1$.

Let $n>1$ and assume $\exists k\in\Bbb N\colon n+k\in T$, say $n+k=t\in T$. If $k>1$, then $(n+1)+(k-1)=t$ and we are done. If $k=1$, then there exists $m\in\Bbb N$ with $t+m\in T$. At any rate, $\exists k\in\Bbb N\colon (n+1)+k\in T$.

Now the lemma follows by induction.$\square$

Corollary. $S=\Bbb N$. $\square$

| cite | improve this answer | |
$\endgroup$

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.