Non-Trivial Induction Order

Question

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?

Answer 1

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

Answer 2

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.