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

Question

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?

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

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.