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?

Solution 1:

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$.

Solution 2:

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...

Solution 3:

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.}$$