Mathematical Induction: A Powerful and Elegant Method of Proof

It is impossible not to fall in love at second sight with mathematical induction. I claim that love at first sight is nigh-on impossible because of the weirdness of induction to the sensibilities of the kid who hasn’t seen it before and because of the fact that everyone’s favorite example with which to introduce induction is that of the sum of the arithmetic sequence. I’ve taught this material it seems like a hundred times, and certainly never miss the chance to hit them with the child Gauss: first using his slick approach and then going at \(1+2+3+\dots\) via induction next. At this point the youths (including, in my university, a plague of computer science kids who just want the ^^$%^&-ing algorithm…) are apt to say, yes, but why? After all we have the slick method of the child Gauss. Well, then we get to second sight (no pun intended): after proving that induction does what it claims — I just don’t like the domino-effect hand-waving and, instead, give ‘em a serious proof by contradiction (you know what I mean: induction is equivalent to the well-ordering of the natural numbers) — we get to the cool stuff, from the number of diagonals in an polygon to the binomial theorem and the number of elements in the power set of a finite set. Even the computer science interlopers gravitate to this business, and yes, for mathematicians-in-the-making it’s true love.

Going beyond the parameters of the now-ubiquitous transition-course for undergraduate mathematics majors, once these tyros have experienced a sequence of requisite epiphanies, e.g. the realization that the art of doing proofs is sublime and seductive and that they need to stop whining and learn to enjoy the exquisite pain of very hard mathematical work, they can wade into the deep waters. Induction, weak or strong (but mainly weak) is everywhere, everywhere, everywhere, and it can be very tricky indeed. I remember many eons ago hitting a nasty exercise in Atiyah-MacDonald (of all places) with double weak induction. Great fun, once the clouds had parted. And in the regular scheme of things, there is of course the great induction playground of elementary combinatorics (“discrete methods” in my department). But in truth it’s all over the place, not just at the algebraic/arithmetic end of the spectrum but even at the analytic/geometric end. We all know that, of course — I, for one, thoroughly enjoy having my real analysis students prove that the product of any finite number of continuous functions is again continuous.

Thus, given the ubiquity and importance of induction, what about a big book devoted to nothing but that? I think it’s a great idea, for at least three reasons. It’s elegant stuff, of course (again, who doesn’t love a good induction proof?). It’s very difficult to find really good examples of the method in action in a serious way (as anyone teaching the aforementioned transition course will probably agree — or maybe it’s just me? I find myself going back again and again to the usual suspects). And the ubiquity and popularity of such things as prep courses for Putnam Examinations, Mathematics Olympiads, and any number of other kindred contests makes for a huge pedagogical playground for induction. So, the book under review hits the target on a number of fronts.

Yeah, it’s good stuff. The authors get off the ground quickly, including in their initial “brief overview” even a bit on transfinite induction. But the thrust of this book is induction of the prosaic kind (weak and strong) and it’s all about problems — as it should be. The authors cover everything, from the needed elementary material to problems coming from major national and even international mathematics competitions; they spend a great deal of time and energy on these tricky problems, all in a pedagogically sound way: the treatment is careful, thorough, and clean. All the details are there, and the prose is clear and to the point. Here are three examples:

Example 7.15 (St. Petersburg) Is it possible to choose several points in space and connect some of them by line segments, such that each vertex is the endpoint of exactly 3 segments, and any closed path has length at least 30? (p. 133)

(The answer is yes: it’s a graph theory business, naturally.)

Problem 5.27 (IMO 2010 Shortlist) A sequence … is defined by \(x_1=1\) and \(x_{2k}=-x_k\), \(x_{2k-1}=(-1)^k x_k\) for \(k\geq 1\). Prove that for all \(n\geq 1\), we have \(x_1+x_2+\dots + x_n\geq 0\). (p. 276)

And finally, from the section on number theory,

Problem 6.44 Prove that for all positive integers \(m\), there exists an integer \(n\) such that \(\varphi(n)=m!\). (p. 316)

Good, no?

So, what more needs to be said? It’s an eminently useful, well-written, and fun book, with huge pedagogical appeal: lots and lots of examples and problems to do. I expect to use my copy a lot.

Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.