Strengthening the Induction Hypothesis - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T06:45:56Z http://mathoverflow.net/feeds/question/31699 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis Strengthening the Induction Hypothesis Tony Huynh 2010-07-13T13:01:34Z 2012-03-24T20:37:46Z <p>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),</p> <p><strong>Theorem.</strong> 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. </p> <p><strong>Question 1.</strong> What are some other nice examples of this phenomenon?</p> <p><strong>Question 2.</strong> Under what conditions is the strategy of strengthening the induction hypothesis likely to work?</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/31701#31701 Answer by Péter Komjáth for Strengthening the Induction Hypothesis Péter Komjáth 2010-07-13T13:31:34Z 2010-07-13T13:31:34Z <p>One well known example is the estimate $\log(n)&lt;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)&lt;\frac{1}{n}$ which is $\left(1+\frac{1}{n}\right)^n&lt; e$ when reordered. </p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/31703#31703 Answer by David Speyer for Strengthening the Induction Hypothesis David Speyer 2010-07-13T14:01:26Z 2010-07-13T18:06:53Z <p>Here is a bit of advice that took me a while to learn: </p> <blockquote> <p>You don't need to know what you are proving when you start to write a proof by induction. </p> </blockquote> <p>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.</p> <p>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. </p> <p>I'd been thinking about writing a blog post on this, but all the examples I know are really technical.</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/31709#31709 Answer by Hans Lundmark for Strengthening the Induction Hypothesis Hans Lundmark 2010-07-13T14:31:30Z 2010-07-13T14:31:30Z <p>Here's a small example from the book <a href="http://www-cs-faculty.stanford.edu/~knuth/gkp.html" rel="nofollow"><em>Concrete Mathematics</em></a>:</p> <p>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> <p>p. 97, exercise 3.25: Prove or disprove that the Knuth numbers satisfy $K_n \ge n$ for $n\ge 0$.</p> <p>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$.</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/31712#31712 Answer by Jeff Strom for Strengthening the Induction Hypothesis Jeff Strom 2010-07-13T14:56:51Z 2010-07-13T14:56:51Z <p>Paul Goerss' review of the book "Differential algebras in topology" by David Anick contains the following remark:</p> <p>"...the spaces $D_k$ are constructed and analyzed inductively, with surely the largest inductive hypothesis that I have ever seen."</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/31737#31737 Answer by muad for Strengthening the Induction Hypothesis muad 2010-07-13T18:01:56Z 2010-07-13T18:01:56Z <p>There is a detailed exposition on this proof technique in Knuth's book <em>Surreal Numbers</em>. The characters of the book develop the idea gradually.</p> <p>In <em>Algebra with Galois theory</em> 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.</p> <p>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 <a href="http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html" rel="nofollow">Deforestation: transforming programs to eliminate trees</a>.</p> <p>Another example from computing is the method of reducibility candidates (which is explained in <a href="http://www.paultaylor.eu/stable/Proofs+Types.html" rel="nofollow">Proofs and Types</a>) used to prove strong normalization for various forms of lambda calculus.</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/31739#31739 Answer by Neel Krishnaswami for Strengthening the Induction Hypothesis Neel Krishnaswami 2010-07-13T18:12:35Z 2010-07-13T18:12:35Z <p>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 <em>without lemmas</em>. 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.</p> <p>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 <em>subformula property</em>, 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 <em>fails</em> for the induction rule. In terms of the sequent calculus, you can give a left rule for which looks like this: </p> <p>$$\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}$$</p> <p>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.</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/31753#31753 Answer by T. for Strengthening the Induction Hypothesis T. 2010-07-13T19:25:10Z 2010-07-13T19:25:10Z <p>I think the role of the base case of the induction is crucial and should be separated from the analysis. </p> <p>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. </p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/40021#40021 Answer by S. Carnahan for Strengthening the Induction Hypothesis S. Carnahan 2010-09-26T13:08:12Z 2010-09-26T13:08:12Z <p>If $p$ is a polynomial in $n$ real variables that is positive on $[0,1]^n$, the integral <code>$\int_{[0,1]^n} p(\mathbf{x})^s d\mathbf{x}$</code> 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 <a href="http://en.wikipedia.org/wiki/Bernstein-Sato_polynomial" rel="nofollow">Bernstein-Sato theorem</a>: there is a polynomial $b(s)$ and a (noncommutative) polynomial <code>$D(x_i, \frac{\partial}{\partial x_i}, s)$</code>, 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. </p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/40035#40035 Answer by jp for Strengthening the Induction Hypothesis jp 2010-09-26T16:53:43Z 2010-09-26T16:53:43Z <p>A classical example is the proof of <a href="http://en.wikipedia.org/wiki/Sperner%27s_lemma" rel="nofollow">Sperner's Lemma</a> 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.</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/40685#40685 Answer by Andrew D. King for Strengthening the Induction Hypothesis Andrew D. King 2010-09-30T23:48:55Z 2010-09-30T23:48:55Z <p>The 5-choosability proof is also my favourite. It's really a classic example.</p> <p>My example involves bounding the combination of two global invariants by bounding the combination of two local invariants.</p> <p>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.</p> <p>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.</p> <p>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$.</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/40688#40688 Answer by Nick S for Strengthening the Induction Hypothesis Nick S 2010-10-01T00:04:06Z 2010-10-01T00:04:06Z <p>Very simple example:</p> <p>$1+ \frac{1}{4} + \frac{1}{9} + ...+ \frac{1}{n^2} &lt; 2$</p> <p>cannot be proved by induction for obvious reasons, but </p> <p>$1+ \frac{1}{4} + \frac{1}{9} + ...+ \frac{1}{n^2} &lt; 2-\frac{1}{n}$</p> <p>is an easy induction problem.</p> <p>: 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.</p> http://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis/92104#92104 Answer by I. J. Kennedy for Strengthening the Induction Hypothesis I. J. Kennedy 2012-03-24T20:37:46Z 2012-03-24T20:37:46Z <p>Here's a simple example I found in <em>Mathematical Miniatures</em>.</p> <p>$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} &lt; \frac{1}{\sqrt{3n}}$</p> <p>The induction step comes down to wanting $$\frac{2n+1}{2(n+1)} &lt; \frac{\sqrt{3n}}{\sqrt{3(n+1)}}$$</p> <p>which unfortunately is not true. However if the induction hypothesis is slightly strengthened to </p> <p>$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} \le \frac{1}{\sqrt{3n+1}}$</p> <p>the induction runs smoothly.</p> <p>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.</p>