# Is Cauchy induction used for proofs other than for AM–GM?

The proof by Cauchy induction of the arithmetic/geometric-mean inequality is well known. I am looking for a further theorem whose proof is much neater by this method than otherwise.

• Every midpoint convex function is rationally convex (Jensen convex): Midpoint-Convex and Continuous Implies Convex at Math.SE. – Martin Sleziak Nov 25 '16 at 11:52
• I didn't know what Cauchy induction was, but the various examples of the thread suggest it plainly. – ACL Nov 25 '16 at 20:13
• If a ring $R$ satisfies $\left(a^2 = 0 \Longrightarrow a=0\right)$ for each $a \in R$, then every nilpotent in $R$ is zero. There is a really easy proof by Cauchy induction (although it doesn't really get longer if you reword it using standard induction). – darij grinberg Nov 26 '16 at 1:21
• I vaguely remember that there may be a solution to Waring's problem along these lines: use Hilbert's identity to show that if Waring holds with exponent $k$, then it holds for exponent $2k$ and then pad out the intermediate exponents in some way... – David Conlon Nov 26 '16 at 22:33
• While not strictly Cauchy induction, I think one of the proofs of the Fundamental Theorem of Algebra is vaguely reminiscent of it: the proof uses induction not on the degree, but on the highest power of 2 dividing the degree. The idea is that passing from a polynomial of degree $n$ to a polynomial of degree $n(n+1)/2$ is actually a reduction step in this style of induction. See an answer to math.stackexchange.com/questions/1354501/…. – KConrad Dec 4 '16 at 4:11

A nice proof by Cauchy induction can be given for the identity $$\|A^n\|=\|A\|^n,$$ which holds for a bounded, self-adjoint operator $A:H\to H$ on a real Hilbert space $(H,\langle\cdot,\cdot\rangle)$. Here $\|\cdot\|$ denotes the operator norm.

Indeed, the inequality $\|A^n\|\le\|A\|^n$ is trivial by submultiplicativity of such norm. Let us turn to the converse inequality: if you know that $\|A^n\|\ge\|A\|^n$, then $$\|A^{n-1}\|\|A\|\ge\|A^n\|\ge\|A\|^n,$$ so the same holds with $n-1$ in place of $n$. Thus it suffices to show that, whenever it holds for $n$, it holds also for $2n$: $$\|A^{2n}\|=\sup_{\|x\|\le 1}\|A^{2n}x\|\ge\sup_{\|x\|\le 1}\langle A^{2n}x,x\rangle=\sup_{\|x\|\le 1}\langle A^nx,A^nx\rangle=\|A^n\|^2\ge\|A\|^{2n}.$$

This last line used Cauchy induction (i.e. the idea to prove $n\Rightarrow 2n$ rather than, e.g., $n\Rightarrow n+1$) in an essential way!

• In the low-chance event that someone else as slow as me reads this answer, it might help to interpolate, before the first inequality in the final display line, the further inequality $\ge\sup_{\|x\|\le 1}(\|A^{2n}x\|\|x\|)$. (Actually, equality holds here.) The existing inequality then can be seen to hold by Cauchy--Schwartz. – John Bentin Nov 26 '16 at 18:19

Assume that $f$ is a function defined in a certain interval $\Delta$ and you want to prove that $$\sum_{i=1}^n f(x_i)\geqslant nf(a),\,a=\frac1n \sum x_i,\tag 1$$ where the numbers $x_i$ in $\Delta$ are arbitrary or satisfy some additional condition U. Example of U would be '$x_i+x_j\leqslant 2b$ for $i\ne j$.' Then Cauchy induction allows to consider only the case $n=2$, which is often handy. In the above example we induct from $n$ to $n+1$ bit tricky: replace two largest numbers to the average and then add the total average.

Specific example: if $x_i$ are non-negative numbers and the sum of any two does not exceed $\pi$, then $\sum \cos x_i\leqslant n \cos a$.

In the case when there is no condition U, we have simply Jensen inequality, which gives AM-GM for $f=-\log$ or for $f=\exp$. Of course, for other convex functions $f$ it also works. Moreover, you may define, as Martin Sleziak writes in the comment, 'midpoint convexity' of $f$ by $f(x)+f(y)\geqslant 2f\left(\frac{x+y}2\right)$ (this is equivalent to convexity under additional assumptions like continuity), and deduce (1) by Cauchy induction.

• Both midpoint convex and Jensen convex seem to be used quite often. But baby convex is certainly a very nice name. – Martin Sleziak Nov 25 '16 at 14:26
• Condition U does have to satisfy certain conditions itself, like being convex, right? – darij grinberg Nov 26 '16 at 1:22
• @darijgrinberg of course it is not arbitrary. Strictly speaking, we have a sequence of conditions $U(n)$, and they should be chosen so that both forward and backward steps of Cauchy induction work somehow. – Fedor Petrov Nov 26 '16 at 8:29

This is due to Noga Alon, recently popularized by Gil Kalai. I started a big-list thread motivated by this proof, and the answer by Federico Poloni reminded about this question.

Theorem. Let $G=(V,E)$ be a bipartite $r$-regular multigraph. Then $E$ is a union of $r$ perfect matchings.

Proof. At first, we prove it when $r$ is a power of 2, by induction. Base $r=1$ is clear. If $r>1$ is even, the number of edges in each connected component is even (sum up degrees of one part.) Take an Eulerian cycle in every connected component and color edges alternatively, we partition $E$ onto two $r/2$-regular multigraphs. Apply induction proposition for them.

Now assume that $r$ is not a power of 2. Take large $N$ and write $2^N=rq+t$, $0<t<r$. Replace each edge of our multigraph onto $q$ edges, also add extra edges formed by arbitrary $t$ perfect matchings. This new multigraph may be partitioned onto $2^N$ perfect matchings, and if $N$ is large enough, some of them do not contain extra edges. So, we have found a perfect matching in initial graph, removing it and repeating $r$ times gives a required decomposition.

• Nice! So this theorem can be proven without Hall... – darij grinberg Jun 14 '17 at 11:01
• @darijgrinberg There is a short Hall-avoiding proof by studying the Birkhoff polytope of doubly stochastic matrices. Namely, replace a regular multigraph to a graph with positive weights on edges such that the total weight of edges in any vertex equals 1. If the graph is a forest, it is already a perfect matching (look at isolated vertex and its neighbor). If it has a cycle, replace the weights along the cycle by $+t,-t$ alternatively so that the minimal weight becomes equal to 0. Proceed this way. – Fedor Petrov Jun 14 '17 at 11:28
• The first stage looks pretty close to the stages "true for $n=0$" and "true for $n=k$ implies true for $n=2k\,$" of Cauchy induction. I wonder whether the second stage can be easily modified to fit the format of the other stage: "true for $n=k+1$ implies true for $n=k\,$". – John Bentin Jun 14 '17 at 18:32
• @JohnBentin it is 'full Cauchy induction': for given $k$, if true for some $n>n_0(k)$, then true for $k$. – Fedor Petrov Jun 14 '17 at 19:26

Here is a use of the Cauchy induction method to show a function that almost looks like a non-archimedean absolute value is a non-archimedean absolute value. [EDIT: This is used in the course of one of the proofs that the absolute value on a finite extension of a nonarchimedean complete valued field extends to an absolute value on each finite extension of that field.]

For a field $K$ suppose a function $|\cdot| \colon K \rightarrow \mathbf R_{\geq 0}$ is multiplicative, satisfies $|n| \leq 1$ for all integers $n$, and $$|x+y| \leq C\max(|x|,|y|)$$ for all $x, y \in K$ and some $C > 0$. We want to refine this to $|x+y| \leq \max(|x|,|y|)$ for all $x, y \in K$. That is, we want to prove we can take $C = 1$ in the above inequality. (Note: For $K = \mathbf R$ the usual absolute value satisfies $|x+y| \leq 2\max(|x|,|y|)$ for all $x$ and $y$ in $\mathbf R$ and we can't replace $2$ with $1$ in that bound; thus the hypothesis $|n| \leq 1$ for all $n \in \mathbf Z$ is important.)

We of course can assume $C > 1$, since otherwise what we want is obvious.

First let's try something that will not work out (I think), in order to appreciate the Cauchy method that comes later. By induction on the number of terms it is not hard to show for all $x_1,\ldots,x_n$ in $K$ that $|x_1+\cdots + x_n| \leq C^{n-1}\max(|x_1|,\ldots,|x_n|)$. Then, using $n+1$ terms, $$|(x+y)^n| = \left|\sum_{k=0}^n \binom{n}{k}x^ky^{n-k}\right| \leq C^n\max_{0 \leq k \leq n} \max(|x|,|y|)^n$$ since $|\cdot|$ is multiplicative and binomial coefficients have absolute value at most 1 by hypothesis. The left side above is $|x+y|^n$ by multiplicativity, so $|x+y|^n \leq C^n\max(|x|,|y|)^n$. Take $n$th roots and we get $|x+y| \leq C\max(|x|,|y|)$, so we are back where we started and gained nothing.

Here is another approach. If $n = 2^r$ is a power of 2 then any sum of $n$ terms $x_1 + \cdots + x_n$ in $K$ can be broken up into two sums with $n/2$ terms each, so by induction or $r$ we get $$|x_1 + x_2 + x_3 + \cdots + x_{2^r}| \leq C^r\max(|x_1|,|x_2|,|x_3|, \ldots,|x_{2^r}|)$$
for all $x_1,\ldots,x_{2^r} \in K$.
For $x$ and $y$ in $K$ let's apply this to $|(x+y)^{2^r-1}|$. The binomial expansion $$(x+y)^{2^r-1} = \sum_{k=0}^{2^r-1} \binom{2^r-1}{k}x^ky^{2^r-1-k}$$ has $2^r$ terms. In the $k$-th term we have $|\binom{2^r-1}{k}| \leq 1$ by hypothesis. Therefore $$|x+y|^{2^r-1} \leq C^r\max_{0 \leq k \leq 2^r-1} \max(|x|^k|y|^{2^r-1-k}) = C^r\max(|x|,|y|)^{2^r-1}.$$ Taking $(2^r-1)$-th roots of both sides, $$|x+y| \leq C^{r/(2^r-1)}\max(|x|,|y|).$$ Letting $r \rightarrow \infty$, $C^{r/(2^r-1)} \rightarrow 1$ and we get $|x+y| \leq \max(|x|,|y|)$.

While we did not actually need to go back and prove anything for a general number of terms that is not a power of $2$, I still think this argument has the spirit of the Cauchy idea.

• Could you give an example of a nontrivial such nonarchimidean valuation? – John Bentin Nov 26 '16 at 8:50
• @JohnBentin see my edit to the first paragraph: every extension of a nonarchimedean complete absolute value on a field to a finite extension of that field is potentially a nontrivial example in the course of proving that extension really is an absolute value on the larger field, i.e., that it satisfies the non-archimedean triangle inequality after proving the other properties of being an absolute value. – KConrad Nov 26 '16 at 16:35

Another inequality can be proved by Cauchy induction :$$\prod_{i=1}^n(x_0+x_i)\geqslant\left(x_0+\prod_{i=1}^nx_i^{1/n}\right)^n\quad\text{for all}\quad n=1,2,...\;\text{and}\; x_0,...,x_n\geqslant0.$$ Details can be found here. I don't see a different easy way to do it. While this involves a geometric mean, it doesn't look much like the AM–GM inequality, because there is a product on both sides. Perhaps, though, it could be derived from AM–GM.

Edit:$\quad$As I have later learned, it can indeed be derived from AM–GM. First, write this standard inequality with variables $x_1,...,x_n>0$. Now replace each $x_i\,$ ($i=1,...,n$) respectively by $x_0^2/(x_0+x_i)$. In parallel, replace each $x_i$ respectively by $x_0x_i/(x_0+x_i)$. Add the two consequent inequalities, and the result easily simplifies to the inequality above. (The extension to $x_1,...,x_n\geqslant0$ is trivial.)