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?
Best Answer
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$.