What are some examples of induction where the base case is difficult but the inductive step is trivial? According to Wikipedia:

...proofs by mathematical induction
  have two parts: the "base case" that
  shows that the theorem is true for a
  particular initial value such as n = 0
  or n = 1 and then an inductive step
  that shows that if the theorem is true
  for a certain value of n, it is also
  true for the value n + 1. The base
  case is often trivial and is
  identified as such, although there are
  cases where the base case is difficult
  but the inductive step is trivial.

What are some examples of proofs by induction where the base case is difficult but the inductive step is trivial?
 A: The Product Rule, $$(f_1f_2\cdots f_n)'=f_1'f_2\cdots f_n+\cdots+f_1f_2\cdots f_n'$$ To prove the base case, $n=2$, $(fg)'=f'g+fg'$, you need to apply the definition of the derivative, and properties of limits. But then you can deduce the $n+1$ case very simply from the base case and the induction hypothesis: $$(f_1f_2\cdots f_{n+1})'=\bigl((f_1f_2\cdots f_n)(f_{n+1})\bigr)'=(f_1f_2\cdots f_n)'f_{n+1}+(f_1f_2\cdots f_n)f'_{n+1}, {\rm\ etc.}$$
A: Caratheodory theorem about convex hull.
The base case is to show that a point in the convex hull of $n+2$ points of a $n$ dimentional affine space, is in fact in the convex hull of $n+1$ points.
A: When proving by induction on $n$ that the usual topology on $\mathbf R^n$ is the only  Hausdorff topology on $\mathbf R^n$ that makes it a topological vector space over $\mathbf R$ with its usual topology, the base case $n=1$ is actually the hardest case. (The same result is true with $\mathbf R$ replaced by $\mathbf C$ or any other nondiscrete complete valued field, such as the $p$-adic numbers.) Note the discrete topology on $\mathbf R^n$, for $n \geq 1$, does not make $\mathbf R^n$ a topological vector space (where the scalars $\mathbf R$ have their usual topology).
I once read a manuscript where the author proved this result, by induction on $n$ of course, but the proof was unusually short. Since I knew that the base case is harder than the rest of the argument, I concentrated my attention there and found a mistake.
A: Bolzano-Weierstrass theorem: every bounded sequence in $\mathbb{R}^n$ has a convergent subsequence.
The inductive step is very easy and most of the work is in showing that this is true for $n=1$.
A: The proof that all horses are the same color. The base case is $n=2$; prove that every set of $2$ horses is a set of horses all of the same color. If you can prove that, the induction step is a breeze; in any set of $n+1$ horses, remove one horse, the rest are all of the same color, then put that horse back in and remove a different one, again getting a set of horses all of the same color, and note that since $n+1\ge3$ there's at least one horse in both of the size $n$ sets, so all $n+1$ horses are of the same color. 
But that base case is really, really difficult! 
In fact, you might say it's a horse of a different color...
A: The proof of the infinite Ramsey theorem for $n$-tuples and $k$ colors is usually started with an induction on the number of colors $k$. The base case $k=2$ requires a technical second induction on $n$. The inductive step for $k$ is, by comparison, almost trivial.
A: Pick's Theorem says that the area of a lattice polygon is the number of interior lattice points, plus half the number of lattice points on the boundary, minus 1. It can be proved by induction on the number of sides of the polygon. It's not hard to prove that if you divide a lattice polygon up into smaller lattice polygons, and if the formula holds for the smaller polygons, then it holds for the original polygon. That's the induction step in the proof of Pick's Theorem. The base case is proving it's true for triangles, and that's harder. Indeed, the way I know for proving it for triangles uses the result of the induction step!
A: Others examples are:

*

*The base case for Taylor's theorem with integral remainder. The induction step can be done by integrating by parts. The base case actually is the Fundamental Theorem of Calculus.


*The base case of the generalised Euclid's lemma: if a prime p divides a n-product of integers , then it divides at least one of them . The induction step is easier than the base case.


*The completeness of $\mathbb{R}^n$ (the proof can be done without induction, but still the example is  interresting)


*The " Kernel Lemma " (it seems, it hasn't a specific name in most languages, except in French; known as "Le Lemme des Noyaux"): $\bigoplus_{i=1}^n \ker \left[ P_i(f) \right] = \ker \left[ \left( \prod_{i=1}^n P_i \right)(f) \right],$ where $P_1,\ldots,P_n$ are coprime polynomials, and $f$ an endomorphism of a vector space over a field.
A: Define the function $E(x)=\displaystyle\sum_{i=0}^\infty\frac{x^n}{n!}$ (you can forget about the convergence issue for this problem). To prove the fact that $E(mx) = E(x)^m$ for all integers $m$, you need a relatively straightforward induction step. The more laborious part is proving that $E(x+y)=E(x)E(y)$, which allows for the induction. I got this example from "How We Got from There to Here: A Story of Real Analysis" by Eugene Bowman and Robert Rogers.
