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?
Best Answer
Here is a bit of advice that took me a while to learn:
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.