Proofs by induction [closed]

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.

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!

-

closed as not a real question by Felipe Voloch, Mariano Suárez-Alvarez♦, Harry Gindi, Joel David Hamkins, Kevin H. LinApr 18 '10 at 8:58

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

Unless you define what you mean by «explanatory» it is impossible to know what you have in mind... –  Mariano Suárez-Alvarez Apr 17 '10 at 21:22
Also, in my specialty (evolutionary partial differential equations), almost every single existence/stability result ever put to paper is a proof by induction. Whether a proof is explanatory has relatively little to do with the technique employed (induction, contradiction, etc.) but more about the presentation by the author. I think this question is ill-posed. –  Willie Wong Apr 17 '10 at 21:30
I'm sorry for the vague us of "explanatory", Mariano. I was just intending to try to appeal to people's intuitions about what is meant by "explanatory", if people have any, as I don't want to presuppose a particular theory of mathematical explanation. Willie, I'd be interested in knowing some more about what you mean by "presentation of the author". Thanks for your help. –  Lea M Apr 17 '10 at 21:39
I agree that the question needs more -- um -- explanation. (In fact, the downvote is mine.) However, I think there is a question lurking in here, and I disagree with MSA's comment above in that I think I may know what the OP has in mind. I plan to post an answer in the near future. It would be nice if the question would stay open... –  Pete L. Clark Apr 17 '10 at 21:41
Answers evince the fact that 'explanatory' is easily confused with 'constructive', if in fact they are different concepts... –  Mariano Suárez-Alvarez Apr 17 '10 at 22:30

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

-
#6 has a visual inductive proof which I find somewhat insight-generating, constructed by arranging i x i x i blocks for 0 <= i <= n diagonally on a (1 + 2 + ... + n)^2 board. –  Tom Crockett Jul 10 '11 at 9:43

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.

-
Your second paragraph here neatly answers the question Lea addressed to me. A proof that just lumps technical step one after another can certainly be logically sound, but it is the extra touch of the mathematician who writes about the intuition or the big picture of the proof that makes it understandable. To take an extreme example: Christodoulou's recent proof on black hole formation in relativity has its bulk (~300pps) in one big induction argument. Chapters 3 - 15, where the induction step is shown, is not explanatory at all. It is the three short chapters 1, 2, 16 that explains. –  Willie Wong Apr 17 '10 at 22:38

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.

-
Perhaps it is reasonable to regard Goodstein's Theorem and the Paris-Harrington Theorem as examples of "noninductive" theorems about natural numbers? After all, they cannot be proved by induction over the natural numbers ... –  Simon Thomas Apr 17 '10 at 23:13
Simon, I would regard Goodstein's theorem as more inductive than usual, since it has the natural structure of induction up to epsilon zero. :) –  John Stillwell Apr 17 '10 at 23:21
Fair enough ... –  Simon Thomas Apr 17 '10 at 23:36

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

-
Right -- see Theorem 4 in the first handout I linked to in my answer above. –  Pete L. Clark Apr 18 '10 at 6:04
this is not induction on n. –  Martin Brandenburg Apr 18 '10 at 9:23
I never said it was induction on $n$, although I can rename the variables to make it induction on $n$. The theorem that I am proving is my last sentence. The sum of the first $n$ $k$th powers is a polynomial in $n$ of degree $k+1$. This can be proven by induction on $k$. I illustrated the inductive step for $k=2$, but it is clear that it works for any $k$ by (strong) induction. Moreover, this inductive proof shows how the polynomial can be computed. –  Tony Huynh Apr 18 '10 at 13:47

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://math.uga.edu/~pete/3200induction.pdf

and

http://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.

-
I was going to put Gauss' first proof of QR on the list of not-very-insightful inductive proofs in my answer, but it seemed out of proportion to the other examples so I didn't bother. Glad you mentioned it! –  KConrad Apr 17 '10 at 23:39

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.

-
So what is the difference between 'explanatory' and 'constructive'? –  Mariano Suárez-Alvarez Apr 17 '10 at 21:56
You have a point. This is definitely a constructive proof. The question made me think of a talk I saw Art Benjamin based on his book Proofs that Really Count. In the book, he presents combinatorial proofs of a number of claims that are often proven by induction. The combinatorial proof has the benefit that you understand why the result is true as you prove it instead of just pushing around symbols. This is an example of a proof by induction that I feel doesn't have that kind of issue. –  Jamie Weigandt Apr 17 '10 at 22:09
I would have let the base case be $n=1$, i.e., covering a $1\times1$ grid with one square removed with no triominos. But perhaps that is slightly pathological. –  Harald Hanche-Olsen Apr 17 '10 at 22:56