44
$\begingroup$

What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ where the number of terms depends on $n$ and you're doing induction on $n$?

Postscript three years later: I see that I phrased this last part in a somewhat clunky way. I'll leave it there but rephrase it here:

--- that are not instances of induction on the number of terms in a sum?

  • 11
    I suffered greatly the first time I saw induction, because it was also my first serious exposure to $\sum$ notation, and the two pills were too much to swallow at once.2012-05-14
  • 1
    Good question! The "sum" examples are of necessity *all* of the collapsing sum kind. So although induction is needed in principle, they are not persuasive.2012-05-14
  • 2
    [This](http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/) is quite nice IMO.2012-05-15
  • 7
    @Ragib, The Blue Eyed Islanders problem is a horrible example of induction because it is very confusingly about knowledge as being separate from truth, which is a huge distraction.2012-05-15
  • 1
    @OldPro Yet it gives an example of how subtle mathematical inductions can be. And it's just plain fun.2012-11-12

19 Answers 19