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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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$