Induction is one of the most common tools is mathematics, and everybody knows the ordinary induction and the strong induction. However, in some proofs induction is applied in an unexpected and elegant way. This can happen in two ways:
- The proof uses a special form of induction.
- The variable that is inducted on is surprising.
To clarify what 1 and 2 mean, let me give an example of both.
- Cauchy's proof of the arithmetic-geometric inequality $\frac{x_1+\cdots+x_n}{n}\geq \sqrt[n]{x_1\cdots x_n}$ proceeds by showing that the case $n=2^k$ implies the case $n=2^{k+1}$ and that the case of $n=k$ implies the case $n=k-1$. This is an unconventional type of induction that turns out to be suitable for this theorem (though it is not the only way to prove it).
- A proof of the van der Waerden theorem (given here) goes as follows: Assume that $W(r,k-1)$ exists. By induction on $n$ we see that there exists a number $N=N(r,k,n)$ such that if the set $[1,N]\cap \mathbb{N}$ is colored with $r$ colors, one can either find a monochromatic arithmetic progression of length $k$ or $n$ arithmetic progressions of length $k-1$ each of which is monochromatic but has a different color. Then taking $n=r+1$ we get that $W(r,k)$ is finite and the ordinary induction on $k$ continues.
Question: What other examples are there of proofs of famous and non-trivial results where induction is crucial in the argument and it is of the form 1 or 2?
The types of induction include for example induction on prime numbers, induction on the rational numbers, inductions based on the parity of the variable, inductions where the cases are not proved in an incresing order (as in example 1 above), and so on.
By a surprising variable of induction I mean one that is not given in the theorem and adding this to the theorem is not obvious (so a non-example would be proving an inequality of three variables by inducting on the number of varibles).
Best Answer
From van der Waerden's book I learned this proof of the fundamental theorem of algebra, where the induction is on the exponent of 2 in the prime decomposition of the degree of the polynomial:
To show that every real polynomial $p(x)=x^n+t_{n-1} x^{n-1}+\cdots +t_0$ has $n$ roots in the complex numbers $\mathbb C$, write $n=2^k\cdot u$ with $u$ odd, and induct on $k$. For $k=0$, the degree is odd, and you have a root in $\mathbb R$. For $k>0$, let $(a_1,\ldots, a_n)$ be the roots of $p$ in some extension field; prove that the polynomial with roots $b_{ij}=a_i+a_j$ has real coefficients and use the induction hypothesis on $\binom{n}{2}$ to show that the $b_{ij}$ are in $\mathbb C$. Do the same for $c_{ij}=a_i a_j$, and then compute $a_i$ and $a_j$ from $b_{ij}$, $c_{ij}$ using square roots only.