Understanding Less Frequent Form of Induction? (Putnam and Beyond) I won't paste the question here since my problem is not a technical one but a conceptual one. 
Book is here: (Page 22 of the pdf)
I do not understand why it is necessarily to induct $2^{k}$ to show $2^{k+1}$ when the proof follows up with inducting backwards from (n+1) to (n). 
I recall a similar induction problem where backwards induction itself already suffice.
Why it is necessarily to show the former $2^{k}$? Doesn't showing (n+1) to (n) already include in-itself the powers of $2$?
 A: Please do insert more details in your question.
In any case, forward-backward induction is a very common concept, so here's my answer:
It is not sufficient to be able go from $n+1$ to $n$ because you don't have a large value of $n$ to start.
The forward part of going from $2^k$ to $2^{k+1}$ ensures that you have arbitrarily large values of $n$ from which you can go downwards.
A: As I explained in an answer to a similar question, this type of induction is most conceptually viewed as a sort of interval (or segment) induction. Intuitively, the essence of the matter is extremely simple: $\:\mathbb N\:$ is the only unbounded initial segment of $\:\mathbb N.\:$ Here are the details:
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 $ $ (sketch) $\ $ 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\:$ to all $\rm\:n\ge m\:$ by $\rm\:n\not\in S\:\Rightarrow\:n\!+\!1\not\in S.\ \ $  QED
Corollary $ $ If, additionally, $\rm\:S\:$ is unbounded then $\rm\:S = \mathbb N.\ \ $ QED
In your case let $\rm\: S\ne \{\ \}\:$ be the set of naturals where the proposition is true. We know by hypothesis that $\rm\:S\:$ satisfies the Lemma so $\rm\:S\:$ is an initial segment of $\mathbb N.\:$ Furthermore, by hypothesis $\rm\:n\in S\:\Rightarrow\:2\:\!n\in S,\: $ hence $\rm\:S\:$ is unbounded. Therefore $\rm\:S = \mathbb N\:$ by the Corollary. 
