# 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?

-

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. – Andrés E. Caicedo Jul 13 '10 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 '11 at 16:13

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.

-
I think you mean $\le$ in your statement or else it fails for $n=1.$ – Daniel Parry Sep 6 '15 at 19:01
You can also do it without induction, using a telescope sum: $\displaystyle\sum_{k=1}^{n} \frac{1}{k^2} = 1 + \sum_{k=2}^{n} \frac{1}{k^2} < 1 + \sum_{k=2}^{n} \frac{1}{k(k-1)} = 1 + 1 - \frac{1}{n} = 2 - \frac{1}{n}$. – Martin Brandenburg Mar 6 at 16:34

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 '10 at 11:20
In the base case the LHS=$-\infty$ but the RHS=0. As $n$ increases the LHS is trying to catch up with the RHS. That's why induction fails because the LHS increases more. – Fan Zheng Apr 24 '15 at 22:20

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

-

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 '10 at 19:42

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.

-

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 '10 at 19:04

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/… – j.p. Sep 26 '10 at 16:56

Theorem (difficult): Every planar graph can have its edges directed such that the indegree of each vertex is $\leq 3$.

Strengthening (easy): Every plane graph can have its edges directed such that the indegree of each vertex is $\leq 3$, and the indegree of each vertex on the boundary is $\leq 2$.

Proof: Let $G$ be a plane graph and let the boundary vertices be denoted $x_1, x_2, x_3, \dots, x_n$ in cyclic order. Define the subgraph $H < G$ by deleting $x_2$ and all incident edges. Then we use the induction hypothesis to legitimately direct the edges of $H$, and extend this to $G$ by having $x_2$ have two incoming edges (from $x_1$ and $x_3$) and all other edges be outgoing. The base case is trivial, so the result follows by induction on the order of $G$. QED

Interestingly, when the original problem was set on a selection test for determining the British IMO team, only one person found this elegant proof (which I believe was unknown to the problem-setters, who instead had a meticulous argument involving Euler's formula.

-
@gowers -- This seems compatible with your theory of splitting questions...? – Adam P. Goucher Jun 8 '15 at 12:31
I can't follow why the proof gives that $G$ satisfies the theorem statement, can you explain? For example, it seems like the proof would construct a star graph with all edges pointing to the center, whose in-degree is then too high. – usul Jun 8 '15 at 17:26
Oh, I guess that the proof assumes that all vertices have degree at least 3, but this is okay since you can fully triangulate the graph (and delete the excess edges afterwards). – Adam P. Goucher Jun 8 '15 at 19:48
That makes sense to me, but I'm worried that interior vertices could get too many in-directed edges. If $x_2$ has an edge to a vertex not on the boundary who already has $3$ incoming edges, then we would be adding a fourth incoming edge to that vertex...? – usul Jun 8 '15 at 21:32
Oh, it is a nice proof! General combinatorial fact is the following: if there are at most $d\cdot |U|$ edges joining vertices of any subset $U\subset V(G)$, then $G$ has an orientation with indegrees at most $d$. The condition is necessary for obvious reasons. – Fedor Petrov Sep 6 '15 at 10:38

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

-

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 '10 at 20:15
@Peter: Agreed. This similar question has more examples of this. – Tony Huynh Jul 14 '10 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 '10 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 '10 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.

-

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

-

Euler's formula $V-E+F=2$ for convex polytopes has a trivial inductive proof after we replace polytopes to connected planar graphs (remove edges until you get a tree), and even more trivial if we replace 2 to $1+C$, where $C$ is a number of connected components of arbitrary planar graph (remove edges until you get a graph without edges). Note that such operations on a ser of polytopes are not well defined. This is probably a reason why Euler did not prove this fact.

-

A nice exercise is to prove that the recurrence $T(x+y)\le T(x)+T(y)+\lg(\min\{x,y\})$ is such that $T(n)=O(n)$. (Note that $\lg$ is log base 2.)

The strengthen induction hypothesis is $T(n)\le n-\lg n-1$. Once we have assumed this, we get \begin{eqnarray*} T(x+y) & \le & T(x)+T(y)+\lg(\min\{x,y\})\\ & \le & (x-\lg x-1)+(x-\lg y-1)+\lg(\min\{x,y\})\\ & = & (x+y)-\lg(x+y)-1+(\lg(x+y)+\lg(\min\{x,y\})-\lg x-\lg y-1)\\ & = & (x+y)-\lg(x+y)-1+\lg\frac{(x+y)\min\{x,y\}}{2xy}\\ & \le & (x+y)-\lg(x+y)-1. \end{eqnarray*}

The reason I like example is that it seems that the "-1" is needed.

-