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?