Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.