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 PrincipleContents
root
2002-06-10