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?
 A: 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 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.
A: Very simple example:
$$1+ \frac{1}{4} + \frac{1}{9} + \cdots+ \frac{1}{n^2} < 2$$
cannot be proved by induction for obvious reasons, but 
$$1+ \frac{1}{4} + \frac{1}{9} + \cdots+ \frac{1}{n^2} \leq 2-\frac{1}{n}$$ 
is an easy induction problem.
[Edit]: 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.
A: 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: 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$.
A: 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. 
A: 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."
A: 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. 
A: 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: 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 set of polytopes are not well defined. This is probably a reason why Euler did not prove this fact. 
A: 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$.
A: 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.
A: 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.
A: 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.
A: 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.
A: 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 $\text{“}-1\text{''}$ is needed.
