# 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$?

-

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.

-
In this case (the arithmetic mean–geometric mean inequality) doubling is easy to handle, and going down single steps is not particularly complicated using a specific term, but going up single steps is harder. –  Henry May 24 '12 at 21:55
Just to make it a little more clear, what you do in this proof is that since you cannot do a forward induction for all natural numbers (easily?) you prove it for all natural powers of 2, and then by backward induction fill in the gap. –  Keivan May 24 '12 at 21:56
I understand now, thanks for the responses. –  Mat.S May 24 '12 at 22:02

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.

-
Thanks for the background! –  Mat.S May 25 '12 at 0:00
Here is a sample application proving $\rm\,gcd(a,b)=1\,\Rightarrow\,gcd(a^n,b^n)=1.$ –  Bill Dubuque Jul 5 '12 at 4:25