Unconventional types of induction

Question

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:

1. The proof uses a special form of induction.
2. 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).

Answer 1

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.

Answer 2

I have always been impressed by the following construction of graphs with arbitrarily large chromatic number and girth. The construction I will mention is due to Nesetril-Rodl, and the the first such construction is due to Laszlo Lovasz.

The construction is based on hypergraphs, and indeed the only known constructions build recursively using hypergraphs. Call a hypergraph a $[p,k,n]$-hypergraph if it is a $k$ uniform with no $p$-cycles and chromatic number at least $n$. Suppose for a fixed $p$ and $n$ you can produce a $[p,K,n]$-hypergraph for all values of $K$.

The inductive step is to use this to show a $[p+1,k,n]$-hypergraph exists, but in doing so it requires that a $[p,K,n]$-hypergraph for several values of $K$ which are (much) larger than $k$. To start the induction, one needs a $[1,k,n]$- hypergraph which is given by the $k$ uniform graph with $(k-1)(n-1) + 1$ vertices.

The construction can also be found in section 2.3 here.

Answer 3

The negative solution of Burnside's problem by Novikov and Adjan is an outstanding example of use of complicated induction. Quoting from Wikipedia's entry on Adjan:

"The solution of the Burnside problem was certainly one of the most outstanding and deep mathematical results of the past century. At the same time, this result is one of the hardest theorems: just the inductive step of a complicated induction used in the proof took up a whole issue of volume 32 of Izvestiya, even lengthened by 30 pages."

Answer 4

George Andrews's paper Pfaff's method (I): The Mills-Robbins-Rumsey determinant contains, according to the author, "the world's most cumbersome mathematical induction ever." It uses induction to simultaneously prove 20 different identities.

Answer 5

Laver tables often involve unconventional types of induction. In fact, constructing the Laver tables and proving that they are self-distributive involves an unusual double and triple induction.

Consider the following Lemmas.

$\textbf{Lemma 1}$ For all $N$ there exists a unique binary operation $*$ on $\{1,...,N\}$ such that

1. $x*1=x+1$ whenever $x<N$

2. $N*x=x$ for all $x$ and

3. $x*y=(x*(y-1))*(x+1)$ whenever $x<N$ and $y>1$.

One proves Lemma 1 for each $x*y$ by a double induction which is descending on $x$ and for each $x$ the induction is ascending on $y$.

In fact, many results about Laver tables are proven using a descending then ascending double induction.

$\textbf{Lemma 2}$ For all $N$ the algebra $(\{1,...,N\},*)$ satisfies the self-distributivity identity $x*(y*z)=(x*y)*(x*z)$ if and only if $x*N=N$ whenever $x\in\{1,...,N\}.$

The direction $\rightarrow$ in Lemma 2 is straightforward, but the direction $\leftarrow$ is by descending induction on $x$, then for each $x$ one proceeds by ascending induction on $y$ and for each $y$, one uses ascending induction on $z$. Notice how one uses a descending induction for each variable in $x*(y*z)$ to the left of the operation $*$ and one uses an ascending induction for each variable to the right of the operation $*$. Similarly, one uses a descending induction for $x$ in $x*y$ in Lemma 1 and one uses an ascending induction on $y$ in $x*y$ in Lemma 1 because $x$ is on the left side of $*$ and $y$ is on the right side of $*$.

Lemma 2 is needed to prove the following theorem.

$\textbf{Theorem}$ The algebra $(\{1,...,N\},*)$ satisfies the self-distributivity identity $x*(y*z)=(x*y)*(x*z)$ if and only if $N=2^{n}$ for some $n$.

The self-distributive algebra $(\{1,...,2^{n}\},*)$ is known as the $n$-th classical Laver table.

Answer 6

1) Prove a relative property $P(M,N)$ of a compact manifold $M^n$ embedded in $N^{n+1}$.

2) Prove for a sphere $S^n$ the property $P(S^n)$.

3) Conclude that property $P$ holds for any compact manifold.

This is an induction of sorts: the role of the usual integer is played by the complexity of the manifold. Rather then concluding a property $P(n)$ from the properties $P(k),k<n$, going from smaller integers to a larger one, you conclude the property of a more complicated manifold from the properties of simpler ones.

Answer 7

In the theory of crystal bases of quantized enveloping algebras due to Kashiwara, he has a so-called "grand-loop" argument, consisting of 14 induction statements. Each is a conventional induction, on the face of it, but the method of proof interleaves them, so that the $l$th case of one statement also features in the proof of the $l$th case of others. The proof takes just over 13 pages.

(Reference: pages 489-503 of "On crystal bases of the Q-analogue of universal enveloping algebras." Duke Math. J. 63 (1991), no. 2, 465–516.)

Answer 8

The following induction method is almost never mentioned:

Step 1: Prove something is true for $n = i$, for $i$ with $1 \le i \le k-1$, where $k \ge 2$ may be arbitrarily chosen.

Step 2: Assuming it's true for $n$, prove it's true for $kn + i$ for all $i$ with $0 \le i \le k-1$.

This induction method gives an, in my eyes, pretty proof of the existence of a representation of any positive integer in any base $b \ge 2$. Funnily enough, to prove this induction method works requires (ordinary) induction.