# Proof verification: Showing, through Induction, that a set $S=\mathbb{N}$

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?

• 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$ – Ulivai May 22 at 19:16
• 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. – Mando May 22 at 19:19
• +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. – gen-z ready to perish May 22 at 19:29
• @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$. – Deepak May 22 at 19:34
• @Mando Your base case should actually be $2$. Applying (ii) to $k=2$ will reveal that $1\in S$. Pretty sneaky, huh.... – gen-z ready to perish May 22 at 19:47

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.

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$$.

• Thank you for your answer. This is good. I am unpacking it a bit for the minutiae but I follow the logic. – Mando May 22 at 19:58
• 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. – Mando May 22 at 20:18
• What is “backwards proof by induction using contradiction”? – gen-z ready to perish May 22 at 21:26
• "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. – fleablood May 22 at 21:54

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$$