2 added 323 characters in body

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.

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)$. 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 realized the analogy with differential and integral calculus. It's completely analgous 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://www.math.uga.edu/~pete/3200induction.pdf

and

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

1

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.

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)$. 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 realized the analogy with differential and integral calculus. It's completely analgous 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://www.math.uga.edu/~pete/3200induction.pdf

and

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