Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

One of the standard proofs for the Arithmetic Mean-Geometric Mean Inequality is via the following induction route:

Let $n$ be the number of (non-negative) variables. It is proved for $n=1,2$ (straightforward), and then it is proved that if it is valid for $n \ge 2$ then it is valid for $2n$ and $n-1$.

This implies that the inequality is valid for all $n$ which are powers of 2, and since any positive integer is less than some power of 2, the inequality follows for all $n \ge 1$.

Are the more examples of this kind of induction (backward induction or $n \to 2n$), or in general not the usual $n \to n+1$ or $1,2,\cdots,n \to n+1$ induction schemes?

share|improve this question

2 Answers 2

This isn't too far from the usual scheme, but if you want to prove that every amount exceeding 7 cents can be made from 3-cent and 5-cent stamps, you can establish base cases 8, 9, and 10, and then prove that if you can do $n$, you can do $n+3$ by just adding one more 3-cent stamp.

Similarly you can show 6 divides $n^3-n$ by doing base cases 1, 2, ..., 6 and then doing $n\to n+6$.

share|improve this answer

Goodstein's theorem is generally thought of as being proved by induction over ordinals, but since all the ordinals involved are countable you could also think of it as an (extraordinarily complicated) example of this.

share|improve this answer

Your Answer

 
discard

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.