Introduction Crunch Appetizers Fly in the soup Entrees Icing on the cake References
Introduction

Mathematical induction is a beautiful tool by which one is able to prove infinitely many things with a finite amount of paper and ink. It works by exploiting underlying structure: a complex and unwieldy problem can sometimes be broken apart along its fault lines so as to leave behind many smaller problems, each of which is more easily solved. Induction is one method of finding such fault lines and organizing the smaller pieces of a larger problem. Often, the simpler structure of the small pieces permeates the whole, and a complicated structure can be seen to operate based on the same simple rules that govern its pieces. This can lead to results that are both powerful and counter-intuitive.

Induction is only one of many techniques through which one may attempt to wrestle with infinity in finite terms (which is to say: with home field advantage), but it holds a rather distinguished position in mathematics. Conveniently, it requires very little background knowledge to learn, and for this reason it is often taught in high school and could reasonably be included in an elementary school curriculum. Its home is in the natural numbers : 1, 2, 3, 4, . . ., which are, barring geometrical objects, arguably the most intuitive of all mathematical ob ects. Despite its apparent simplicity, its use in contemporary mathematics is widespread. But perhaps most tellingly, a casual lunchtime conversation with my colleagues about induction revealed that everyone seemed to have their own “induction story”, a tale of their first encounter with or first appreciation of mathematical induction. It is clear that induction holds a special place in the mathematician’s heart, and so it is no surprise that it can be the source of so much beauty, confusion, and surprise.