Many, many math books have an introduction to induction. Try Courant and Robbins, What is Mathematics?, section I.2. See also Martin Gardner, Martin Gardner, Mathematical induction and colored hats, Penrose Tiles to Trapdoor Ciphers, chapter 10.
