ABSTRACT
One of the most powerful tools of mathematics---and, arguably, the most-used tool in discrete mathematics---is induction (from the verb induce, not induct!). This chapter defines induction in both its most common and most general forms, then provides fourteen puzzles and a theorem illustrating some of the many ways induction can be used. The puzzles engage the reader in designing point-sets, re-arranging seats, splitting numbers evenly, turning off light bulbs, moving a baby frog to a clearing, posting guards in a gallery, finding a path through cell towers, weighing bagels, summing fractions, tiling with triominoes and pricing a sales tour in Russia. The theorem uses induction to show that Ramsey numbers exist and in particular that the Ramsey number R(s,t) is bounded by a binomial coefficient.
