## Strengthening the Induction Hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This has a chance of succeeding because you have more to work with in the induction step. My favourite example of this is Thomassen's beautiful proof that every planar graph is 5-choosable. The proof is actually pretty straightforward once you know what you should be proving. Here is the strengthened form (which is a nice exercise to prove by induction),

Theorem. Let $G$ be a planar graph with at least 3 vertices such that every face of $G$ is bounded by a triangle (except possibly the outer face). Let the outer face of $G$ be bounded by a cycle $C=v_1 \dots v_kv_1$. Suppose that $v_1$ has been coloured 1 and that $v_2$ has been coloured 2. Further suppose that for every other vertex of $C$ a list of at least 3 colours has been specified, and for every vertex of $G - C$, a list of at least 5 colours has been specified. Then, the colouring of $v_1$ and $v_2$ can be extended to a colouring of $G$ with the specified lists.

Question 1. What are some other nice examples of this phenomenon?

Question 2. Under what conditions is the strategy of strengthening the induction hypothesis likely to work?

-

One well known example is the estimate $\log(n)<1+\frac{1}{2}+\cdots+\frac{1}{n}$ for the harmonic series. It is easier to show $\log(n+1)$ as a lower bound, for an inductive step from $n-1$ to $n$ it suffices to show that $\log(n+1)-\log(n)<\frac{1}{n}$ which is $\left(1+\frac{1}{n}\right)^n< e$ when reordered.

-
 This is an interesting anomaly, since the base ($n=0$) case for the stronger lower bound is an equality. – S. Carnahan♦ Sep 26 2010 at 11:20

Here is a bit of advice that took me a while to learn:

You don't need to know what you are proving when you start to write a proof by induction.

The following method isn't needed for easy problems, but it has several times gotten me a lemma that wouldn't yield to any other means. After you've worked on the problem for a week or so and have a good feel for it, write down all the conditions that seem to be relevant. Write down all the implications you can prove of the form "If the conditions in set $S$ hold for some values of the parameters, then the conditions in set $T$ hold for some other values." Discard any in which set $S$ can be shrunk, or $T$ enlarged. Now, draw a graph with arrows between the sets. You are looking for a loop in this graph, a path from your hypothesis to the loop, and a path from the loop to your conclusion. If you find one, then you have a potential proof by induction, assuming that your parameters "decrease" as you go around the loop.

This is the other part of the trick. When you start this procedure, there is no need to decide which order you are using on the set of parameters. Wait until you've found the loop! Then the loop gives you a specific recursion on your parameter set, and you can try to find a well-order with respect to which this recursion is decreasing.

I'd been thinking about writing a blog post on this, but all the examples I know are really technical.

-
A post on this would be interesting. "all the examples I know are really technical": Don't let this discourage you. – Andres Caicedo Jul 13 2010 at 14:06
Now there's a piece of advice that any mathematician or computer scientist would do well to print out and put on the wall over his/her desk!! <a href="homepages.inf.ed.ac.uk/bundy/">Alan Bundy</a> works on automated proofs by induction; I don't know whether he had thought of this. Regarding the main question, most of theoretical computer science is about huge proofs by induction; strengthening the hypothesis is usually a matter of course. – Paul Taylor Mar 3 2011 at 16:13

Here's a small example from the book Concrete Mathematics:

p. 78: Let $K_0=1$ and $K_{n+1}=1+\min(2 K_{\lfloor n/2 \rfloor}, 3 K_{\lfloor n/3 \rfloor})$ for $n\ge 0$. ("One of the authors of this book has modestly decided to call these the Knuth numbers.")

p. 97, exercise 3.25: Prove or disprove that the Knuth numbers satisfy $K_n \ge n$ for $n\ge 0$.

Induction fails when trying to prove $K_n \ge n$ directly (as explained in the text on p. 79), but works easily for the stronger statement $K_n > n$.

-

Paul Goerss' review of the book "Differential algebras in topology" by David Anick contains the following remark:

"...the spaces $D_k$ are constructed and analyzed inductively, with surely the largest inductive hypothesis that I have ever seen."

-

There is a detailed exposition on this proof technique in Knuth's book Surreal Numbers. The characters of the book develop the idea gradually.

In Algebra with Galois theory by Emil Artin (and probably all the other books), any two splitting fields of of f(x) over F are isomorphic is proved neatly in by generalizing the predicate to say that if two fields are isomorphic then they are extended to isomorphic splitting fields. The same sort of generalization repeatedly occurs in correctness arguments for simple recursive programs.

This proof technique also begets a programming technique: Adding a new parameter to a recursive function (which corresponds to generalizing the induction predicate) will often let you give more efficient algorithms. As a simple example consider a converting leaves of a tree to a list from Deforestation: transforming programs to eliminate trees.

Another example from computing is the method of reducibility candidates (which is explained in Proofs and Types) used to prove strong normalization for various forms of lambda calculus.

-
 As a simpler example for the programming case, just consider how you reverse a list in a strict functional programming language. – Zsbán Ambrus Jul 13 2010 at 19:04

The very simplest example I know of this phenomenon is the proof of the commutativity of addition (on $\mathbb{N}$). It's a fun little exercise to try and prove it without lemmas. That is, try and find an inductive argument that doesn't call for a nested induction or use an auxilliary fact like the associativity of addition.

From a proof-theoretic perspective, it's possible to show that the need to strengthen induction hypotheses is an inherent property of the (finitary) induction rule. Sequent calculi for first-order logic satisfies property called the subformula property, which says that every theorem of FOL has a proof only involving subformulas of the theorem to be proved (counting $A[t/x]$ as a subformula of $\forall x.\;A$). However, the subformula property fails for the induction rule. In terms of the sequent calculus, you can give a left rule for which looks like this:

$$\frac{\Gamma \vdash B(0) \qquad \Gamma, B(j) \vdash B(s\;j) \qquad \Gamma, B(i) \vdash C }{\mathrm{nat}(i), \Gamma \vdash C}$$

Reading the sequent bottom-up, note that the formula $B$ "comes out of nowhere" -- it's not a subformula of either $C$ or any of the existing hypotheses $\Gamma$. You just have to make it up to solve your problem! This is why computerized theorem provers are useless at inductive proofs: we don't have good heuristics for coming up with induction hypotheses.

-
 Is there a visible manifestation (or explanation) of the subformula property in ordinary, informal but first-orderizable proofs? – T. Jul 13 2010 at 19:42

I think the role of the base case of the induction is crucial and should be separated from the analysis.

Conceivably you could get some proof-theoretic understanding of "induction without the base", i.e., the phenomenon of how strengthening property $P_{\rm weak}$ to $P_{\rm strong}$ can make the implication $P(n) \to P(n+1)$ easier to prove. However, $P_{\rm strong}(1)$ and $P_{\rm weak}(1)$ are different, and it is hard to imagine how a theory of the base case could possibly be set up. Maybe when considering families of $P$ something could be said, but otherwise one is up against the full strangeness of the finite and accidental.

-
In the opposite direction, I find it remarkable how often base cases can be avoided/simplified. Proofs will put a fair amount of effort into showing $P(1)$ as a base case, not noticing that $P(0)$ in fact makes sense, and is trivially true, and that the induction case step is sufficent to show $P(0) \Rightarrow P(1)$. Of course, this only works if all definitions have been given in forms that get trivial cases “right”; but the nicest forms of definitions usually do. Whenever the base case proof seems to have a similar flavour to the induction step, it's worth looking to see if this happens. – Peter LeFanu Lumsdaine Jul 13 2010 at 20:15
@Peter: Agreed. This similar [question](mathoverflow.net/questions/11964/…) has more examples of this. – Tony Huynh Jul 14 2010 at 9:49
@T. Interesting. I agree that a proof-theoretic understanding of the base case would be difficult to set up. However, I am guessing that in most instances weak(1) and strong(1) would both be 'trivial' (whatever that means). This of course raises the separate question of examples of induction proofs where the inductive step is easy, but the base case is hard. – Tony Huynh Jul 14 2010 at 12:54
I see the weak and strong base cases as being trivial only in the sense that they usually lead to small finite computations. Recognizing a pattern $P$ in the base case(s) that generalizes smoothly can be harder than finding the proof of $P(n) \to P(n+1)$ when $P$ is given. Roughly, it's the difference between finding a solution and verifying one (similar to NP > P). – T. Jul 14 2010 at 16:23

If $p$ is a polynomial in $n$ real variables that is positive on $[0,1]^n$, the integral $\int_{[0,1]^n} p(\mathbf{x})^s d\mathbf{x}$ converges for $s$ a complex number with positive real part. In order to continue this function of $s$ to a meromorphic complex function elsewhere, you can employ the Bernstein-Sato theorem: there is a polynomial $b(s)$ and a (noncommutative) polynomial $D(x_i, \frac{\partial}{\partial x_i}, s)$, such that $b(s)p(\mathbf{x})^s = D\cdot p(\mathbf{x})^{s+1}$. This lets you expand the integral in terms of $p(\mathbf{x})^{s+1}$, but the new integral has extra terms attached. In order to make an inductive proof of continuation work, you need to prove that a more general class of integrals can be continued, namely products of terms of the form $p(\mathbf{x})^s$ with polynomials.

-

A classical example is the proof of Sperner's Lemma where one replaces the weaker condition of the existence of a simplex with all colors by showing that the number of such simplexes is odd.

-
 I just read a related question where Sperner's Lemma is also given as an example (but I think it fits better here), see mathoverflow.net/questions/21214/… – jp Sep 26 2010 at 16:56

The 5-choosability proof is also my favourite. It's really a classic example.

My example involves bounding the combination of two global invariants by bounding the combination of two local invariants.

Reed's $\omega$, $\Delta$, $\chi$ conjecture proposes that $\chi \leq \gamma := \lceil \frac 12 (\omega+\Delta+1)\rceil$. A favourite trick when bounding the chromatic number is to consider a minimum counterexample, remove one or more stable sets (which become colour classes), and prove (or pray) that the bounding invariant drops by the number of stable sets you remove.

But it's hard to make the maximum degree drop by 2, and/or make the clique number drop by 1 -- this is what you need when you remove a stable set in this case. Instead, let the invariant be the maximum over all vertices of $\gamma$ for the graph induced on the closed neighbourhood of $v$ (meaning the degree of $v$ plus the size of the largest clique containing $v$, plus one, rounded up). In other words, $\max_v \gamma(G[\bar N(v)])$. Now when you remove a stable set the invariant is easier to control, and you can ignore a vertex whose closed neighbourhood is properly contained in the closed neighbourhood of another vertex.

In the setting of claw-free graphs with stability number $\leq 3$, this was the only way we could prove Reed's conjecture. There are lots of base cases, most notably graphs with stability number $2$.

-

Very simple example:

$1+ \frac{1}{4} + \frac{1}{9} + ...+ \frac{1}{n^2} < 2$

cannot be proved by induction for obvious reasons, but

$1+ \frac{1}{4} + \frac{1}{9} + ...+ \frac{1}{n^2} < 2-\frac{1}{n}$

is an easy induction problem.

: Forgot to add this, while the example is very simple, I like the fact that it is easy to understand (before solving the problem) why induction cannot work in the first example and why it could work in the stronger case.

-

Here's a simple example I found in Mathematical Miniatures.

$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} < \frac{1}{\sqrt{3n}}$

The induction step comes down to wanting $$\frac{2n+1}{2(n+1)} < \frac{\sqrt{3n}}{\sqrt{3(n+1)}}$$

which unfortunately is not true. However if the induction hypothesis is slightly strengthened to

$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} \le \frac{1}{\sqrt{3n+1}}$

the induction runs smoothly.

By the way, it's mentioned in the book that Pólya refers to this phenomenon of strengthening the induction hypothesis as "the researcher's paradox", although it doesn't seem the phrase has caught on.

-