Assume $S \subseteq \mathbb N$ such that:
- $\forall k \in \mathbb N :2^k \in S$
- $\forall k \ge 1: k \in S \implies k-1 \in S$
Show that $S =\mathbb N$.
It's left to show that $\mathbb N \subseteq S$.
Let $P(n)$ be the proposition such that $\left\{ 2^k-n, ...,2^k\right\} \subseteq S$.
The base case is true since $P(0)$ means $\left\{ 2^k\right\} \subseteq S$ which is true by the hypothesis.
Assume $P(n)$ does hold and consider $P(n+1)$,from the assumption $\left\{ 2^k-n, ...,2^k\right\} \subseteq S$ which implies $2^k-n \in S$ From the second property of $S$ it's clear that $2^k-(n+1)= 2^k-n-1 \in S$ and so $\left\{ 2^k-(n+1), ...,2^k\right\} \subseteq S$. Since this is true for all natural $n$ so $S =\mathbb N$.
Edit:
Another way I tried: Let $P(n)$ be the proposition such that $\left\{ 0, ...,2^n\right\} \subseteq S$.
The base case is true since $2^0 \in S$ which is true by the first property of $S$ and from the other property, we see that $0 \in S$.
Assume $P(n)$ does hold and consider $P(n+1)$,from the assumption $\left\{ 0, ...,2^n\right\} \subseteq S$.The set $\left\{0,...,2^{n+1}\right\}$ can be written as $\left\{0,...,2^{n}\right\} \cup \left\{2^{n}+1,...,2^{n+1}\right\}$,again from the first property of $S$, $2^{n+1} \in S$,the second property implies $2^{n+1}-1 \in S$,continuing this way we see that $\left\{2^{n}+1,...,2^{n+1}\right\} \subseteq S$,and so $$\left\{0,...,2^{n+1}\right\}=\left\{0,...,2^{n}\right\} \cup \left\{2^{n}+1,...,2^{n+1}\right\}\subseteq S$$
It would be highly appreciated if someone checks the validity of the proofs.
You might consider the following: Let $n \in \mathbb{N}$. If $n$ is a power of two we are done. Otherwise $n=2^ka$ with $(a,2)=1$ for some $k$. Since $2^a > a$ for all $a$ by a simple induction, $2^ka<2^{k+a} \in S$. and by property $(2)$, $n \in S$.