Induction proof: $S$ contains powers of 2 and predecessors implies $S={\bf N}$ Let $S$ be a subset of $\mathbb{N}$ such that
$$2^k\in S\quad\forall\ k\in\mathbb N$$
and,
$$k\in S\Rightarrow k-1\in S\quad\forall\ k\ge2,k\in\mathbb N$$
Show by induction that $S=\mathbb N$.
 A: Hint $\ $ If one views this as a sort of interval (or segment) induction, then it becomes obvious, namely $\Bbb N$ is the only unbounded initial segment of $\Bbb N.$ Below is the simple proof. 
Lemma $\rm\ S\subset \mathbb N\:$ satisfies $\rm\:n+1\in S\:\!\Rightarrow n \in S\,\ $ iff $\rm\,\ S\:$ is an initial segment of $\:\mathbb N$ 
Proof $ $ (hint) $ $ If $\rm\:S\ne \mathbb N\:$ then $\rm\:S = [0,m)\:$ for the least $\rm\:m\not\in S,\:$ since by induction, nonmembership ascends from $\rm\:m\:$ by $\rm\:n\not\in S\:\Rightarrow\:n+1\not\in S\:$ (contrapositive of the hypothesis).
Corollary $ $ If, additionally, $\rm\:S\:$ is unbounded then $\rm\:S = \mathbb N$
In your case, $\rm\,S\,$ is an initial segment by your second hypothesis and the Lemma, and $\rm\: S\ne \{\ \}\:$ is unbounded via the hypothesis $\rm\:n\in \Bbb N\:\Rightarrow\:2^n\in S.$ Therefore, by the corollary, $\rm\, S = \Bbb N.$
Notice how abstracting the matter set-theoretically helps to make clearer the key structure.
See also this closely related question, where it is referred to as Cauchy's method of induction. Sometimes it is called back-and-forth induction. It occurs frequently  in competition problems.
A: $$(1)\,\,2^1=2\in S\Longrightarrow 2-1=1\in S$$
$$(2)\,\,\text{Suppose }\,\,m\in S\,\,,\,\forall\, m<n$$
Let now $\,t\in\Bbb N\,$ be s.t. $\,2^{t-1}<n\leq 2^t\,$ :
$$2^t\in S\Longrightarrow 2^t-1\in S\Longrightarrow 2^t-1-1=2^t-2\in S,...$$
After no more than $\,2^{t-1}\,$ steps as above, we'll reach $\,2^t-h=n\in S\,,\,0\leq h<2^{t-1}\,$ , and we're done.
Now brush this up a little and formalize.
A: Here is a somewhat bizarre application of mathematical induction.
Let $T$ be a subset of $\Bbb{N}$ consisting of positive integers $k$ satisfying the following proposition:

Whenever $U \subset \Bbb{N}$ satisfies
  
  
*
  
*(Property $A_k$) $2^k \in U$ and
  
*(Property $B$) $l \in U$ and $l \geq 2$ implies $l-1 \in U$,
  
  
  we must have $\{ 1, \cdots, 2^k \} \subset U$.

We claim that $T = \Bbb{N}$ by induction.
1. It is easy to check that $1 \in T$.
2.  Assume $k \in T$. Let $U \subset \mathbb{N}$ satisfies the property $A_{k+1}$ and $B$. Let
$$U' = \{l \in \Bbb{N} : l+2^k \in U \}.$$
Then 


*

*$2^k \in U'$ and hence $U'$ satisfies $A_k$.

*Also, if $l \in U'$ and $l \geq 2$, then $B$ implies that $l+2^k-1 \in U$. Since $l-1 \geq 1$, this implies $l-1 \in U'$. Thus $U'$ also satisfies $B$.


Now induction hypothesis shows that $\{1, \cdots, 2^k \} \subset U'$, or equivalently, $\{2^k + 1, \cdots, 2^{k+1}\} \subset U$. Then $B$ implies $2^k \in U$, or in other words, $A_k$. Thus by induction hypothesis again, $\{1, \cdots, 2^k \} \subset U$. Therefore $k+1 \in T$.
Thus by mathematical induction, $T = \Bbb{N}$.
Finally, let $n \in \mathbb{N}$. Then $n \leq 2^n$, and $S$ satisfies both the property $A_n$ and $B$. Therefore $n \in \{ 1, \cdots, 2^n \} \subset S$ and hence $\mathbb{N} = S$.
A: Hint: First show that if $n\in S$, then $\{1,2,\dots, n\} \subseteq S$. You do this by induction. So the "base" or the start is to note that $n\in S$. Then the "bridge" or the induction step is to note that $k\in A \Rightarrow k-1\in S$. Hence $\{1,2,\dots, n\} \subseteq S$.
Continue: You know that $S\subseteq \mathbb{N}$. So you need just show that all natural numbers are elements of $S$. Let $n\in \mathbb{N}$. You need to show that this randomly given number is in $S$. Now $\lim_{k\to \infty} 2^k = \infty$, so there is a $k\in \mathbb{N}$ such that $2^k > n$. Now for that $k$, $2^k \in S$. So 
$$
n = 2^k - (2^k - n) \in S.
$$
