- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Chapman & Hall/CRC

Publication Date:

2010

Number of Pages:

893

Format:

Hardcover

Series:

Discrete Mathematics and Its Applications

Price:

109.95

ISBN:

9781420093643

Category:

Handbook

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

[Reviewed by , on ]

Michael Berg

12/31/2010

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.

**THEORYWhat Is Mathematical Induction? **Introduction

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

**Foundations**

Notation

Axioms

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

Cardinals

Ordinals

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**

Introduction

Guess the pattern?

A pattern in primes?

A sequence of integers?

Sequences with only primes?

Divisibility

Never a square?

Goldbach’s conjecture

Cutting the cake

Sums of hex numbers

Factoring *x ^{n}* − 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

**APPLICATIONS AND EXERCISES****Identities**

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

**Inequalities**

** **

**Number Theory**

Primes

Congruences

Divisibility

Numbers expressible as sums

Egyptian fractions

Farey fractions

Continued fractions

**Sequences**

Difference sequences

Fibonacci numbers

Lucas numbers

Harmonic numbers

Catalan numbers

Schröder numbers

Eulerian numbers

Euler numbers

Stirling numbers of the second kind

**Sets**

Properties of sets

Posets and lattices

Topology

Ultrafilters

**Logic and Language**

Sentential logic

Equational logic

Well-formed formulae

Language

**Graphs**

Graph theory basics

Trees and forests

Minimum spanning trees

Connectivity, walks

Matchings

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

Complexity

**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

Functions

Calculus

Polynomials

Primitive recursive functions

Ackermann’s function

**Linear and Abstract Algebra**

Matrices and linear equations

Groups and permutations

Rings

Fields

Vector spaces

**Geometry**

Convexity

Polygons

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

**SOLUTIONS AND HINTS TO EXERCISES**

Foundations

Empirical Induction

Identities

Inequalities

Number Theory

Sequences

Sets

Logic and Language

Graphs

Recursion and Algorithms

Games and Recreation

Relations and Functions

Linear and Abstract Algebra

Geometry

Ramsey Theory

Probability and Statistics

**APPENDICES**

ZFC Axiom System

Inducing You to Laugh?

The Greek Alphabet

**References**

**Index**

- Log in to post comments