# 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?

• For all k greater or equal 2: for all n>k, there are no nontrivial solutions to x^n+y^n=z^n – gfes Jun 5 '11 at 1:58

## 7 Answers

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

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

• That's why you typically start with the base case of $n = 1$ instead... – Rahul Jun 4 '11 at 7:47
• @Rahul: I have followed your advice and proved the case of $n=1$, but now the inductive step seems to have got harder... – Henry Jun 4 '11 at 13:45

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.

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

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.

When proving that there is exactly one nondiscrete Hausdorff topology on $\mathbf R^n$ that makes it a topological vector space over $\mathbf R$, 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.)

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.

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!