You are here

Handbook of Mathematical Induction: Theory and Applications

David S. Gunderson
Chapman & Hall/CRC
Publication Date: 
Number of Pages: 
Discrete Mathematics and Its Applications
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Michael Berg
, on

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.

What Is Mathematical Induction?
An informal introduction to mathematical induction
Ingredients of a proof by mathematical induction
Two other ways to think of mathematical induction
A simple example: dice

Gauss and sums
A variety of applications
History of mathematical induction
Mathematical induction in modern literature

Peano’s axioms
Principle of mathematical induction
Properties of natural numbers
Well-ordered sets
Well-founded sets

Variants of Finite Mathematical Induction
The first principle
Strong mathematical induction
Downward induction
Alternative forms of mathematical induction
Double induction
Fermat’s method of infinite descent
Structural induction

Inductive Techniques Applied to the Infinite
More on well-ordered sets
Transfinite induction
Axiom of choice and its equivalent forms

Paradoxes and Sophisms from Induction
Trouble with the language?
Fuzzy definitions
Missed a case?
More deceit?

Empirical Induction
Guess the pattern?
A pattern in primes?
A sequence of integers?
Sequences with only primes?
Never a square?
Goldbach’s conjecture
Cutting the cake
Sums of hex numbers
Factoring xn − 1
Goodstein sequences

How to Prove by Induction
Tips on proving by induction
Proving more can be easier
Proving limits by induction
Which kind of induction is preferable?

The Written MI Proof
A template
Improving the flow
Using notation and abbreviations

Arithmetic progressions
Sums of finite geometric series and related series
Power sums, sums of a single power
Products and sums of products
Sums or products of fractions
Identities with binomial coefficients
Gaussian coefficients
Trigonometry identities
Miscellaneous identities



Number Theory
Numbers expressible as sums
Egyptian fractions
Farey fractions
Continued fractions

Difference sequences
Fibonacci numbers
Lucas numbers
Harmonic numbers
Catalan numbers
Schröder numbers
Eulerian numbers
Euler numbers
Stirling numbers of the second kind

Properties of sets
Posets and lattices

Logic and Language
Sentential logic
Equational logic
Well-formed formulae

Graph theory basics
Trees and forests
Minimum spanning trees
Connectivity, walks
Stable marriages
Graph coloring
Planar graphs
Extremal graph theory
Digraphs and tournaments
Geometric graphs

Recursion and Algorithms
Recursively defined operations
Recursively defined sets
Recursively defined sequences
Loop invariants and algorithms
Data structures

Games and Recreations
Introduction to game theory
Tree games
Tiling with dominoes and trominoes
Dirty faces, cheating wives, muddy children, and colored hats
Detecting a counterfeit coin
More recreations

Relations and Functions
Binary relations
Primitive recursive functions
Ackermann’s function

Linear and Abstract Algebra
Matrices and linear equations
Groups and permutations
Vector spaces

Lines, planes, regions, and polyhedra
Finite geometries

Ramsey Theory
The Ramsey arrow
Basic Ramsey theorems
Parameter words and combinatorial spaces
Shelah bound
High chromatic number and large girth

Probability and Statistics
Probability basics
Basic probability exercises
Branching processes
The ballot problem and the hitting game
Pascal’s game
Local lemma

Empirical Induction
Number Theory
Logic and Language
Recursion and Algorithms
Games and Recreation
Relations and Functions
Linear and Abstract Algebra
Ramsey Theory
Probability and Statistics

ZFC Axiom System
Inducing You to Laugh?
The Greek Alphabet