David S.Gunderson’s Handbook of Mathematical Induction: Theory and Applications is a unique work: in 800 pages and then some, the ostensibly narrow subject of mathematical induction is carefully and systematically expounded, from its more elementary aspects to some quite sophisticated uses of the technique. This is done with a (very proper!) emphasis on solving problems by means of some form of induction or other — Gunderson covers the spectrum: it’s not just weak and strong induction, or multiple induction, it’s even transfinite induction (p. 53ff.), all covered with great zeal and enthusiasm. His scholarship and enthusiasm give the lie in no uncertain terms to any suggestion of narrowness.
The stage for this marvelous excursion is set early on, in the book’s Foreword, written by Béla Bollobás: “What prompts someone to write a book in mathematical induction? To share his passion for mathematics? Gunderson’s passion for all of mathematics is evident. Perhaps this remarkable passion is due to the unusual road he has taken to mathematics. When I first met him, at Emory University in 1993, he was a graduate student. A rather ‘mature’ graduate student; as I learned later, in his youth he had flown aerobatics, and then had been a laborer and truck driver for ten years or so before starting in pure mathematics for the fun of puzzle solving…”
Bollobás then ends the Foreword with the following apt description: “This book is the first example that I know of which treats mathematical induction seriously, more than just a collection of recipes. It is sure to be an excellent student companion and instructor’s guide for a host of courses.”
Gunderson himself notes that his book “contains hundreds of examples of mathematical induction applied in a vast array of scientific areas, as well as a study of the theory and how to find and write mathematical induction proofs.” On this count alone, any of us who regularly teach the undergraduate course aimed at introducing mathematics majors to methods of proof quite simply need to own this book.
The text I used for my most recent iteration of this pedagogical experience (I like to think of it as boot camp for potential future mathematicians) was exceptional in its paucity of good problems on mathematical induction, and it was particularly lousy in its treatment of strong induction. Granted, that book was bad on quite a number of counts and I’ll never use it again… live and learn. My experience is that good books for this course are as rare as odd perfect numbers, and induction is always at huge risk qua appropriate coverage.
In this boot camp course it is imperative that problems should be abundant, both in supply and variety, and should be capable of careful dissection. Gunderson’s supply of such, hitting the mark on both counts, i.e., abundance and variety, make the book invaluable. And the fact that these examples and problems come supplemented by his fine analysis of what’s going on in the shadows only adds to the mix: Gunderson evinces a good deal of fine mathematical culture.
The book is split into three parts, first “Theory,” then “Applications and exercises,” and finally “Solutions and hints to exercises.” That really says it all as far as the book’s structure goes. But let me add that every page of the “Theory” part of the book is dripping with good stuff: Gunderson’s discussions are evocative and thorough and can be appreciated by mathematicians of all sorts, ranging from people who merely wish to improve the way the way they present induction to their students to specialists in discrete mathematics and combinatorics. The latter fact is underscored, for instance, by the inclusion of such topics as graph theory (the stable marriage problem occurs on p. 250), game theory, and Ramsey theory (including coverage of some results by Shelah). Obviously Gunderson’s encyclopedic coverage requires a big book.
What deserves special mention in this connection, is that Gunderson’s choice of areas in which to highlight inductive methods is excellent. His section on linear algebra is a particularly good case in point; consider exercise 666 for example: “Use (Philip) Hall’s theorem (theorem 15.5.1) and induction to show that for m < n, any m×n latin rectangle can be completed to an n×n latin square by the addition of n – m rows.” The solution to this problem is then given in the book’s third section, on p.764, impeccably and crystal-clearly. A beautiful problem is explicated, soup to nuts, in a way that any good and sufficiently mature student can follow.
To boot, and staying within the linear algebra chapter, Gunderson is sure to develop the requisite surrounding material with great care, considerably enhancing the value of his book as a supplementary text, for a huge number of courses, both at an undergraduate and graduate level, the latter more focused in combinatorics direction, of course.
And we have just hit on a particularly exciting feature of the book under review: the second section ends, on p. 398, with exercise 769. Its two page solution occurs on p. 810. Thus about 400 pages of the book, roughly half, are devoted to hints, sketches, and, most often by far, very well-written and detailed expositions of problems’ solutions. It can’t be otherwise, of course, but it is a truly remarkable achievement nonetheless.
Thus, this Handbook of Mathematical Induction is a very welcome addition to the literature, both on account of what it covers and how the material in question is presented. We all need to own it, I think.
Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.