Skip to Content

Handbook of Mathematical Induction

Theory and Applications

By David S. Gunderson

Series Editor: Kenneth H. Rosen

Chapman and Hall/CRC – 2010 – 921 pages

Series: Discrete Mathematics and Its Applications

Purchasing Options:

  • Add to CartHardback: $125.95
    978-1-42-009364-3
    September 13th 2010

Description

Handbook of Mathematical Induction: Theory and Applications shows how to find and write proofs via mathematical induction. This comprehensive book covers the theory, the structure of the written proof, all standard exercises, and hundreds of application examples from nearly every area of mathematics.

In the first part of the book, the author discusses different inductive techniques, including well-ordered sets, basic mathematical induction, strong induction, double induction, infinite descent, downward induction, and several variants. He then introduces ordinals and cardinals, transfinite induction, the axiom of choice, Zorn’s lemma, empirical induction, and fallacies and induction. He also explains how to write inductive proofs.

The next part contains more than 750 exercises that highlight the levels of difficulty of an inductive proof, the variety of inductive techniques available, and the scope of results provable by mathematical induction. Each self-contained chapter in this section includes the necessary definitions, theory, and notation and covers a range of theorems and problems, from fundamental to very specialized.

The final part presents either solutions or hints to the exercises. Slightly longer than what is found in most texts, these solutions provide complete details for every step of the problem-solving process.

Reviews

… a treasure trove for anyone who is … interested in mathematics as a hobby, or as the target of proof automation or assistance. It could also be the basis for a crosscutting course in mathematics, based on seeing how one can apply a single proof technique across the field.

— Simon Thompson in Computing News, May 2011

Gunderson started out collecting some induction problems for discrete math students and then couldn't stop himself, thereafter assembling more than 750 of the addictive things for this handbook and supplementing them with a grounding in theory and discussion of applications. He offers 500-plus complete solutions, and many of the other problems come with hints or references; unlike other treatments, this handbook treats the subject seriously and is not just a ‘collection of recipes’. It’s a book that will work well with most math or computing science courses, on a subject that pertains to graph theory, point set topology, elementary number theory, linear algebra, analysis, probability theory, geometry, group theory, and game theory, among many other topics.

SciTech Book News, February 2011

… a unique work … 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 … 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. … 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 hit[s] the mark on both counts … Gunderson’s discussions are evocative and thorough and can be appreciated by mathematicians of all sorts … [he] develop[s] 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 … a very welcome addition to the literature …

MAA Reviews, December 2010

Contents

THEORY

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

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

Author Bio

David S. Gunderson is a professor and chair of the Department of Mathematics at the University of Manitoba in Winnipeg, Canada. He earned his Ph.D. in pure mathematics from Emory University. His research interests include Ramsey theory, extremal graph theory, combinatorial geometry, combinatorial number theory, and lattice theory.

Name: Handbook of Mathematical Induction: Theory and Applications (Hardback)Chapman and Hall/CRC 
Description: By David S. GundersonSeries Editor: Kenneth H. Rosen. Handbook of Mathematical Induction: Theory and Applications shows how to find and write proofs via mathematical induction. This comprehensive book covers the theory, the structure of the written proof, all standard exercises, and hundreds of application...
Categories: Combinatorics, Mathematics & Statistics, Set Theory, Discrete Mathematics