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

Question

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.

Answer 1

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!

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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