4 deleted 1 characters in body

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?

3 deleted 1 characters in body

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 Thommassen's 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?

2 edited tags