1

Let $~S~$ be a subset of $~N~$ such that

$a)~$ $~2^k\in S~~~\forall~ k\in N$ , and

$b)~$ if $~k\in S~$ and $~k\ge 2~$, then $~k-1\in S~$.

Prove $~S=N~$.

This is a problem from Introduction to real analysis by Bartle and Sherbert. I dont understand how to use principle of mathematical induction in this problem. I also dont understand the relevance of $~a)~$ in this question. Can anyone please help me understand this question and solve it?

Community
  • 1
aditya bhatt
  • 161

2 Answers2

1

Assume if possible, there exists $ x \in \Bbb N$, but $x \notin S$, ofcourse there exists $m,m+1$ such that $ 2^m \lt x \lt 2^{m+1}$. Since $ 2^{m+1} \in S$, so is $ 2^{m+1}-k$ for any $ k \in \Bbb N$ (as long as $ k \lt 2^{m+1}$) from condition (b). So for $k=2^{m+1}-x$, it turns out that $ x \in S$, contradicting our initial assumption and concluding $ S= \Bbb N$.

L--
  • 843
  • I did not understand the part which says "Since 2^(m+1) belongs to S, 2^(m+1) - k belongs to S too for any natural number K." – aditya bhatt Aug 30 '19 at 03:19
1

Let $p$ be any power of $2$ greater than 1. By (a), $p$ is in $S$.

By (b), $p-1$ is in $S$. Then we can repeatedly use (b) to prove that $p-2, p-3, ... , 1$ are all in $S$. (This is where induction is used.)

We can let $p$ be as large a power of $2$ as we like and so every positive integer is in $S$.