29
$\begingroup$

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?

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

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

$\endgroup$
20
$\begingroup$

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

$\endgroup$
3
  • 5
    $\begingroup$ That's why you typically start with the base case of $n = 1$ instead... $\endgroup$
    – user856
    Jun 4 '11 at 7:47
  • 18
    $\begingroup$ @Rahul: I have followed your advice and proved the case of $n=1$, but now the inductive step seems to have got harder... $\endgroup$
    – Henry
    Jun 4 '11 at 13:45
  • $\begingroup$ I did not understand this example. You can not prove the base case since it might not be true. It is possible that two horses have different colors. Ummm... But then someone can ask me to prove that two horses have different colors...but then I might have to study biology. I get it now. $\endgroup$
    – IY3
    May 21 at 4:56
7
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ One could say alternatively that the base case is $n = 1$ (or even $n = 0$, exclamation point which is not factorial!), which is easy, and it's the inductive step that takes work. $\endgroup$
    – LSpice
    May 28 at 22:08
  • 1
    $\begingroup$ @LSpice, I suppose one could say that, but I doubt that anyone ever has. $\endgroup$ May 29 at 1:44
  • $\begingroup$ If I were ever called upon actually to write the inductive proof explicitly, then I would! $\endgroup$
    – LSpice
    May 29 at 19:18
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

When proving by induction on $n$ that the usual topology on $\mathbf R^n$ is the only Hausdorff topology on $\mathbf R^n$ that makes it a topological vector space over $\mathbf R$ with its usual topology, 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.) Note the discrete topology on $\mathbf R^n$, for $n \geq 1$, does not make $\mathbf R^n$ a topological vector space (where the scalars $\mathbf R$ have their usual topology).

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ For some of these, judging the difficulty of the base case depends on what the base case is. For example, the cases $n = 0$ and $n = 1$ of Euclid's lemma and the "kernel lemma", and the case $n = 0$ of completeness of $\mathbb R^n$, are easy. $\endgroup$
    – LSpice
    May 28 at 22:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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