    Next: Strong Principle of Mathematical Up: Induction and Counting Previous: The Pigeonhole Principle   Contents

# Induction

Recall the well-ordering axiom for : that every non-empty subset of has a least element. This may be stated equivalently as: there is no infinite descending chain in ''. We also recall the (weak) principle of induction from before.

Proposition 8.2.1 (Principle of Induction)   Let be a statement about for each . Suppose is true for some and true implies that is true for each . Then is true for all such that .

The favourite example is the Tower of Hanoi. We have rings of increasing radius and 3 vertical rods ( , and ) on which the rings fit. The rings are initially stacked in order of size on rod . The challenge is to move the rings from to so that a larger ring is never placed on top of a smaller one. We write the number of moves required to move rings as and claim that for . We note that , so the result is true for . We take and suppose we have rings. Now the only way to move the largest ring is to move the other rings onto (in moves). We then put the largest ring on rod (in move) and move the smaller rings on top of it (in moves again). Assume that . Then . Hence the result is proven by the principle of induction.    Next: Strong Principle of Mathematical Up: Induction and Counting Previous: The Pigeonhole Principle   Contents
root 2002-06-10