Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

6 Answers 6

up vote 18 down vote accepted

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

share|improve this answer

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

share|improve this answer
2  
That's why you typically start with the base case of $n = 1$ instead... –  Rahul Jun 4 '11 at 7:47
9  
@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.

share|improve this answer

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.

share|improve this answer

The proof of the Hilbert Nullstellensatz (I mean Theorem 4.19) in Eisenbud's book "Commutative Algebra with a view towards Algebraic Geometry" is an example, although maybe not the best. He does induction on the number of generators and the really tricky part is proving it for one generator, the rest is then just an easy induction.

share|improve this answer
3  
This is not the sought type of example since here the adjunction of a single generator is the induction step. The base case is no generators, which is trivial. –  Bill Dubuque Jun 3 '11 at 15:33

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.