568 Appendix B. Mathematical Induction and the Well-Ordering Princip le
(b) Repeat the process from p art (a) to ﬁnd a formula for
+ ···+ n
Then prove your formula.
(16) The Towers of Hanoi. In an ancien t city in India, so the legend goes, monks in a temple have
to move a p ile of 64 sacred disks from one location to another. The d isks are frag ile; only o ne
can be carried at a time. A disk may not be placed on top of a smaller, less valuable disk. In
addition, there is only one other locatio n in the temple (besides the original an d d estination
locations) sacre d en ough that a pile of disks can be placed there.
So the mo nks begin moving d isk s back and forth, between the original pile, the pile at the
new location, and the intermediate location, always keeping the piles in order (largest on the
bottom, smallest on the top). The legend is tha t, before the monks make the ﬁnal move to
complete the pile in the new location, the temple will turn to dust and the world will end .
Generalize this problem to show that if there were n disks to move, it would take a total of
− 1 moves to complete the transfer from one location to another. Should we be worried
about the world coming to an end?
(17) The usual total ordering given by ≤ on Z behaves nicely with respect to addition. Sh ow that
there is no total ordering of Z
that behaves nicely with respect to addition in Z
. That is,
show that there is no total ordering on Z
such that, for all [a], [b], [c] ∈ Z
, if [a] ≤ [b], then
([a] + [c]) ≤ ([b] + [c]). (Hint: If there is such an ordering with  ≤ , use transitivity to
show that  ≤ [n −1], and explain why this leads to a contradiction. Then think about wh a t
similar argument needs to be made to complete the proof.)