Proofs by induction [closed]

Question

Background

I'm interested in the issue of "explanatory" mathematical proofs and would like to try to find out what intuitions mathematicians have about induction, because there seems to be some disagreement as to whether such proofs can ever be explanatory.

Question

Does anyone have any proofs by induction that they think are particularly explanatory, and does anyone have any proofs by induction which they think fail to be explanatory at all? I'd be really grateful if you could post any examples, and also if you could say why you find it/don't find it explanatory.

Thanks for your help.

Comment

I've just been reading through the comments and answers to my question and find them all very helpful. Thank you for taking the time to answer this question and post some interesting examples. Of course, more answers are still welcome!

Answer 1

First of all, the phrase "explanatory" in the question should be replaced with "insightful", as I think you're asking for examples of inductive proofs which give the reader some real understanding of what is going on.

A lot of inductive proofs give insight. Here are a few elementary examples.

1. If $a$ and $b$ are relatively prime positive integers, we can write $ax + by = 1$ for some integers $x$ and $y$. The proof uses induction on $\max(a,b)$ and the inductive step is a replacement of $a$ and $b$ by $a$ and $b-a$ (if $a < b$). The maximum has decreased and this idea in fact leads to Euclid's algorithm, which is the efficient way to practically find $x$ and $y$.

2. For every positive integer $n$, $\cos(nx)$ is a polynomial in $\cos x$ (e.g., $\cos(2x) = 2\cos(x)^2 - 1$). The proof uses the addition formula for $\cos x$ and that idea even shows you how to build the polynomial expression if you want to find it explicitly, and that may be comforting to some people.

3. A polynomial of degree $n$ over a field has at most $n$ roots. The proof shows you how the existence of one root controls the cardinality of the number of possible other roots, using some algebra.

4. Many theorems about polynomials in several variables proceed by induction on the number of variables, and often watching how you can bootstrap a result in $n$ variables to a result in $n+1$ variables gives some kind of nice understanding (if only the understanding that the key case is one variable, suitably formulated). For example, a polynomial in several variables over an infinite field which is identically 0 as a function is the zero polynomial (all coefficients are 0). This is proved by induction and the base case is the previous example, which is really the only involved step.

Here are some theorems where the inductive proof does not give insight.

1. The "exchange lemma" from linear algebra, which is used to justify why any two bases of a finite-dimensional vector space have the same size, has never seemed particularly enlightening to me. It is proved (in part) using induction.

2. Different complex-valued characters of a finite abelian group are linearly independent functions. The proof goes by induction on the number of characters, but I never thought the proof itself really explains the linear independence in an "aha" kind of way. It verifies the truth and then you move on to use it.

3. Cauchy's forwards-backwards inductive proof of the arithmetic-geometric mean inequality is pretty remarkable (since so few theorems are amenable to a forwards-backwards inductive proof [EDIT: an MO question asking for more examples of Cauchy's method is here]), but all the same it doesn't feel like it offers any useful understanding behind the inequality.

4. The sum of the first $n$ positive integers is $n(n+1)/2$. You can check the identity by induction but the mystery remains of how such a formula is found.

5. The sum of the squares of the first $n$ positive integers is $n(n+1)(2n+1)/6$. You can check the identity by induction but again there is no real understanding generated of where the identity comes from.

6. The sum of the cubes of the first $n$ positive integers is $(n(n+1)/2)^2$. You can check the identity by induction but not only does that approach not really explain the formula, it also doesn't explain the surprise that the formula is the square of the formula for the sum of the first $n$ positive integers.

I think I could give an argument by induction to generate infinitely many similar noninsightful proofs by induction starting with item 4, but such an argument wouldn't really give any insight itself, so I will stop here.

Answer 2

A nice simple problem with natural inductive structure is the tower of Hanoi problem. It is not obvious that any solution exists, and it is hard to come up with one explicitly, until you assume that it is possible to move the top $n-1$ disks, after which it is obvious how to move $n$ disks.

There is in fact a "noninductive" solution, but since it takes $2^n-1$ steps, it is preferable not to think about it.

[Added later] Of course, there is really no such thing as a "noninductive" theorem about natural numbers because of the inductive structure of natural numbers themselves. However, the "right" induction in this case exponentially compresses the solution, by suppressing unnecessary details.

Answer 3

Let me see if I can address what I think is the underlying question. Probably most of the proofs by induction you've seen have been of the form "show that this identity $P(n)$ holds," where you are given the identity and must verify $P(1)$ and that $P(n)$ implies $P(n+1)$. It is hard to see how this "explains" identity $P(n)$, since you were given the identity and do not really know "why" it is true.

However, in practice this never happens. A mathematical situation usually gives various indications that it would be amenable to an inductive proof, and then a whole creative process - which students often don't get told about until much after they've seen their first inductive proof - goes into figuring out what the correct statement $P(n)$ should be. This is the part of the proof which is really explanatory, and it's a shame that often it never gets written down.

There are also situations, such as the one jamieweigandt mentions, where a mathematical situation has a natural recursive structure and the proof by induction clarifies the precise nature of this structure. This is somewhat different from the boring inductive proofs people are taught in school and while I don't have a good example at the moment I can assure you that such examples are ubiquitous.

Answer 4

It has been pointed out (see KConrad's answer) that the usual proof that the sum of the first $n$ squares is $n (n+1) (2n+1)/6$ does not give insight. However, I would like to show that a different inductive proof of this fact does give insight. Instead of performing induction on $n$, we can perform induction on the exponent. This approach is very instructive because it shows that the sum of the first $n$ $k$th powers is a polynomial in $n$. It also shows how we can derive the formula for any exponent given that we know the formulas for all the smaller exponents. Thus, in principle the only formula we need to know is that $1 + 2 + \dots n = n(n+1)/2$, which has a beautiful proof by picture here.

I will illustrate this idea by computing the sum of the first $n$ squares.

Observe that

$(n+1)^3-1=\sum_{i=1}^n (i+1)^3 -i^3 = \sum_{i=1}^n 3i^2 + 3i +1$.

Thus,

$3\sum_{i=1}^n i^2 = (n+1)^3-1 - n - 3 \sum_{i=1}^n i$.

However, we have already inductively determined that $\sum_{i=1}^n i = n(n+1)/2$. Thus, substituting and solving yields

$\sum_{i=1}^n i^2 = n (n+1)(2n+1)/6$,

as required.

We can now compute the sum of the first $n$ cubes using the same technique, given that we now know the sum of the first $n$ integers and the sum of the first $n$ squares. This gives a systematic way to compute the sum of the first $n$ $k$th powers, and why it is a polynomial in $n$ of degree $k+1$.

Answer 5

In the last year, I have twice taught a course on mathematical reasoning for future undergraduate math majors. The first time I was surprised by how conceptually difficult induction was for many of the students. I think that part of it is related to the potentially non-explanatory nature of inductive proofs. Let me elaborate and say a little about what I did to try to be more explanatory.

The canonical first induction proof is that for all positive integers $n$, $1 + \ldots + n = \frac{n(n+1)}{2}$. After proving this by induction though, it is irresistible to muddy the waters by mentioning that Gauss, at age $10$, knew a better way. I think it is clear that little Gauss' proof [I assume you know it!] is more "explanatory" than the induction proof. For starters, it allows you to discover what the closed form expression is, and the induction proof does not.

Then we did more complicated such summation formulas, i.e., other power sums and variants of those. It took me a while to realize that, no matter how I had phrased the problem, the students were seriously concerned with "how I knew what to put on the other side". This is notwithstanding the fact that the statement of the problem had the closed form expression on the right hand side. After thinking about this for a while, I realized they had a point: in some sense we are just being asked to check an answer that someone has already found and this "checking" process is not explanatory. (And by the way, "How do you know what to put on the other side?" is much more interesting and natural than the question we are actually asking. We should be encouraging students to ask the natural and interesting questions, rather than discouraging them by asking questions which have less to them than meets the eye.)

I tried to reinforce this by stating in general terms what is done in this sort of induction proof. Suppose that you have two functions $f,g: \mathbb{Z}^+ \rightarrow \mathbb{R}$ and you want to show that for all $n$, $\sum_{k = 1}^n f(k) = g(n)$. Given the principle of mathematical induction, this is equivalent to showing that for all $n$, $g(n+1)-g(n) = f(n+1)$. Now it is clear that if $g$ is something reasonable like a polynomial, there is no "idea" or "explanation" involved in checking this identity: you just do the algebra.

After thinking yet more, I was reminded of calculus. It's completely analogous to answering the question

"Why is it the case that $\int \sec^3 x \ dx = \frac{1}{2} \sec x \tan x + \frac{1}{2} \ln | \sec x + \tan x| + C$?"

by differentiating the right hand side, simplifying, and getting $\sec^3 x$.

I wrote up some thoughts on this in:

http://alpha.math.uga.edu/~pete/3200induction.pdf

and

http://alpha.math.uga.edu/~pete/finitecalc.pdf

Not all induction proofs have this aspect to them, of course, but it certainly is the case that it is often possible to bang out a brute force proof of something by induction and then feel that one has evaded the job of truly understanding why the statement is true. As one extreme example, the first proof of the law of quadratic reciprocity was given by Gauss as a teenager: he proved it by induction! There are now more than one hundred reasonably distinct proofs of QR; the reason for this unusually high multiplicity is, I think, that many people (including myself) have trouble with some of the standard proofs: they do not find them sufficiently explanatory.

Answer 6

The first example of an explanatory proof by induction that comes to mind is the solution to the following problem which originates (to my best knowledge) from Art Benjamin.

By a triomino I will mean an "L-shaped" union of 3 unit squares.

Claim: A $2^n \times 2^n$ grid of unit squares with one square removed can always be covered by triominos.

Proof:

Base case: if $n=1$ then we need to cover a $2 \times 2$ grid with one square removed by triominos. THat is, we need to cover a triomino by triominos. So we're good here.

Induction step: Assume that we can cover any $2^n$ by $2^n$ grid of squares with one square removed by triominos and suppose that we are presented with a $2^{n+1} \times 2^{n+1}$ grid of unit squares.

Separate this into a $2 \times 2$ grid of $2^n \times 2^n$ grids of squares one of which has one square removed. At the place where the four corners of these grids meet, place a triomino in such a way that it covers the corner square of each of the three $2^n \times 2^n$ grids without a square already having been removed.

Now what remains to be covered is the union of four $2^n \times 2^n$ grids of squares each with one square removed, so by the induction hypothesis we can cover it with triominos.