Simple Variations on the Tower of Hanoi to Guide

the Study of Recurrences and Proofs by Induction

Abstract— Background: The Tower of Hanoi problem was The classical solution for the Tower of Hanoi is recursive in
formulated in 1883 by mathematician Edouard Lucas. For over nature and proceeds to first transfer the top n − 1 disks from
a century, this problem has become familiar to many of us peg x to peg y via peg z, then move disk n from peg x to peg
in disciplines such as computer programming, data structures,
algorithms, and discrete mathematics. Several variations to Lu- z, and finally transfer disks 1, . . . , n − 1 from peg y to peg z
cas’ original problem exist today, and interestingly some remain via peg x. Here’s the (pretty standard) algorithm:
unsolved and continue to ignite research questions.
Research Question: Can this richness of the Tower of Hanoi be Hanoi(n, x, y, z)
explored beyond the classical setting to create opportunities for if n > 0
learning about recurrences and proofs by induction? then Hanoi(n − 1, x, z, y)
Contribution: We describe several simple variations on the Tower Move(1, x, z)
of Hanoi that can guide the study and illuminate/clarify the
Hanoi(n − 1, y, x, z)
pitfalls of recurrences and proofs by induction, both of which
are an essential component of any typical introduction to discrete In general, we will have a procedure
mathematics and/or algorithms.
Transfer(n, f rom, via, to) to (recursively) transfer a stack of
Methodology and Findings: Simple variations on the Tower of
Hanoi lead to different interesting recurrences, which in turn height n from peg f rom to peg to via peg via, which will be
are associated with exemplary proofs by induction. named according to the problem variation (it’s Hanoi above),
Index Terms—Tower of Hanoi, Recurrences, Proofs by Induc- and a procedure Move(k, f rom, to) to move the top k (1 in
tion. Hanoi) from peg f rom to peg to (in one move). We will also
use Exchange(i) to exchange disk i and disk 1 (see Section
I. I NTRODUCTION VI).
An analysis of the above strategy is typically presented by
T HE Tower of Hanoi problem, formulated in 1883 by
French mathematician Edouard Lucas [8], consists of
three vertical pegs, labeled x, y, and z, and n disks of different
letting an be the total number of moves, and establishing the
recurrence an = an−1 +1+an−1 = 2an−1 +1, where a1 = 1.
The recurrence is iterated for several values of n to discover
sizes, each with a hole in the center that allows the disk to go
a pattern that suggests the closed form solution an = 2n −
through pegs. The disks are numbered 1, . . . , n from smallest
1. This latter expression for an is proved by induction using
to largest. Initially, all n disks are stacked on one peg as shown
the base case above and the recurrence itself to carry out the
in Figure 1, with disk n at the bottom and disk 1 at the top.
inductive step of the proof.
Perhaps a very intriguing thought is that we need about 585
billion years to transfer a stack of 64 disks 1 if every move
requires one second! This realization is often an aha moment
on a first encounter, and illustrates the impact of exponential
growth on complexity. Though not immediately obvious, other
interesting facts can also be observed (and proved):
0
• Fact 1. When n = 0 (empty stack of disks), a0 = 2 −
1 = 0 is consistent in that we need zero moves to transfer
Fig. 1. Lucas’ Tower of Hanoi for n = 4. all of the disks (none in this case).
n
• Fact 2. The number of moves an = 2 −1 is optimal, i.e.
The goal is to transfer the entire stack of disks to another n
2 − 1 represents the smallest possible number of moves
peg by repeatedly moving one disk at a time from a source to solve the problem (and the optimal solution is unique).
peg to a destination peg, and without ever placing a disk on • Fact 3. Disk i must make at least 2
n−i
moves
top of a smaller one. The physics of the problem dictate that n−1
Pn (exactly
2 in the optimal solution). Observe that i=1 2n−i =
a disk can be moved only if it sits on the top of its stack. The
third peg is used as a temporary place holder for disks while 1 The case of n = 64 is related to a myth about 64 golden disks and the
they move throughput this transfer. end of the world [5].
 2n − 1 for n ≥ 0 (again touching on the notion of the Tower of Hanoi problem satisfies an = p1 an−1 + f (n), where
empty sum when n = 0). p1 = 2 and f (n) = 1, so it’s non-homogeneous, but subtract-
• Fact 4. If we define a repeated move as the act of moving ing an−1 from an gives an − an−1 = 2an−1 − 2an−2 , which
the same disk from a given peg to another given peg, then yields the homogeneous recurrence an = 3an−1 − 2an−2 .
every solution must have a repeated move when n ≥ 4
(pigeonhole principle applied to the moves of disk 1). II. D OUBLE D ECKER
• Fact 5. There is a (non-optimal) solution for n = 3 with
In this variation, called Double Decker, we duplicate every
eight moves none of which are repeated moves.
disk to create a stack of 2n disks with two of each size
The above facts highlight some richness of the problem as
as shown in Figure 2. For convenience of notation, we will
they touch on several aspects of mathematical and algorithmic
consider (only for this variant) that a stack of height n has 2n
flavor which, when pointed out, can be very insightful. For
disks.
instance, Fact 1 is a good reminder of whether to associate
a 0 or a 1 when dealing with an empty instance of a given
problem (empty sum vs. empty product). Fact 2 directs our
attention to what is optimal (not just feasible), and Fact 3 is a
more profound way to address that optimality. Fact 4 is a nice
application of the pigeonhole principle that requires knowledge
of Fact 3; a weaker version can be proved, namely when n ≥ 5
instead of n ≥ 4, if we only rely on Fact 2. Finally, Fact
5 raises the question of how things may be done differently
when we seek non-typical answers. Along those lines, several Fig. 2. Double Decker for n = 3, suggested in [3].
variations for the Tower of Hanoi already exist, which include
a combination of restricted moves, colored disks, multiple A trivial solution to Double Decker is to simply treat it as
stacks, and multiple pegs. For instance, we refer the reader a standard instance of the Tower of Hanoi with 2n disks and,
to [11], [12], [13], [7], [2], [4], [1], [5] for some literature and thus, will need the usual 22n − 1 = 4n − 1 moves. This trivial
examples. solution, however, does not benefit from equal size disks. For
Here we explore several variations while sticking to the instance, if we do not require that disks of the same size must
one stack of disks and three pegs. Our goal is not to extend preserve their original order, then a better solution for Double
the research on the Tower of Hanoi problem but rather Decker is to emulate the standard Tower of Hanoi solution by
provide simple, and yet interesting, variants of it to guide (and duplicate moves, to give a0 = 0, a1 = 2, a2 = 6, ... The
enrich) the study of recurrences and proofs by induction in algorithm is shown below.
introductory discrete mathematics. Therefore, we assume basic DoubleDecker(n, x, y, z)
familiarity with mathematical induction and solving linear if n > 0
recurrences of the form then DoubleDecker(n − 1, x, z, y)
an = p1 an−1 + p2 an−2 + . . . + pk an−k + f (n) Move(1, x, z)
Move(1, x, z)
Several techniques for solving recurrences can be used, such as DoubleDecker(n − 1, y, x, z)
making a guess and Pproving it by induction (e.g. an = 2an−1 +
n The Double Decker recurrence is an = 2an−1 +2 and, since
1), summing up i=0 ia to cancel out factors and express
an in terms of a1 or a0 (e.g. an = an−1 + 2n ), applying a we expect that the solution now requires twice the number
transformation to achieve the desired form (e.g. an = 2an/2 + of original moves, we can use that recurrence to show by
n − 1 and take n = 2k , or an = 3a2n−1 and let bn = log an ), induction that an = 2(2n − 1)  4n − 1. The inductive step
generating (of the form g(x) = a0 + a1 x + a2 x2 + for n = m > 0 will be as follows:
P∞ functionsn
. . . = n=0 an x ), etc... [9].
am = 2am−1 + 2 = 2 · 2(2m−1 − 1) + 2
In particular,
Pkthe method of using the characteristic equa-
tion xk = p
i=1 i x k−i
when f (n) = 0 (homogeneous = 2 · 2m − 4 + 2 = 2 · 2m − 2 = 2(2m − 1)
recurrence) is systematic and suitable for an introductory
level. For example, when an = p1 an−1 + p2 an−2 (a second with a0 = 0 as a base case (examples of making a careful
order homogeneous linear recurrence), and r1 and r2 are choice of base case(s) will follow throughout the exposition).
the roots of x2 = p1 x + p2 , then an = c1 r1n + c2 r2n if Alternatively, we can solve the recurrence itself, by first
r1 6= r2 , and an = c1 rn + c2 nrn if r1 = r2 = r. We changing it into a homogeneous recurrence using the technique
can solve for the constants c1 and c2 by making an satisfy outlined in the previous section, to obtain an = 3an−1 −2an−2
the boundary conditions; for instance, a1 and a2 for n = 1 with the characteristic equation x2 = 3x − 2, and the roots
and n = 2, respectively. This technique can be generalized to r1 = 1 and r2 = 2. So we write an = c1 1n + c2 2n and solve
homogeneous linear recurrences of higher orders. for c1 and c2 using an for two values of n; for instance,
When f (n) 6= 0 (non-homogeneous recurrence), we try to a0 = c1 10 + c2 20 = c1 + c2 = 0
find an equivalent homogeneous recurrence, by annihilating
the term f (n). For instance, the recurrence for the Lucas’ a1 = c1 11 + c2 21 = c1 + 2c2 = 2
which will result in c1 = −2 and c2 = 2. Although only one inductive step is involved (bm and bm−1 ),
An interesting subtlety about Double Decker is to observe an = 2an−1 + 1 was iterated twice “backwards” (a2m−2 ,
that, although we did not require to preserve the original order a2m−1 , and a2m ), which on the one hand is not how one would
of disks (so long no disk is placed on a smaller one), the above typically proceed from an = 2an−1 + 1 to establish some
solution only switches the bottom two disks (disks 2n − 1 truth about an , and on the other hand raises the question of
and 2n). This can be verified by Fact 3: since disk i of the whether multiple base cases are needed (what should the value
original Tower of Hanoi must make 2n−i moves, and that’s of n0 be?). The number of base cases is often a subtle detail
an even number when i < n, disks 2i − 1 and 2i in Double about proofs by induction, and without it, there will be a lack
Decker must do the same, and hence will preserve their order. of insight into the method of mathematical induction itself.
However, disks 2n − 1 and 2n in Double Decker will each Before we address this aspect of the proof, let us establish
make an odd number of moves (namely just 2n−n = 1 move), few base cases to verify their truth: b0 = a2·0 = a0 = 0,
and hence will switch. b1 = a2·1 = a2 = 3, b2 = a2·2 = a4 = 15, ... Typically, a
Therefore, to make Double Decker preserve the original person who is attempting this proof by induction will be easily
order of all disks, we can perform the algorithm twice, which inclined to verify a bunch of base cases, as this feels somewhat
will guarantee that every disk will make an even number of safe for providing enough evidence that the property bn = a2n
moves, at the cost of doubling the number of moves. holds. In principle, however, one should have a systematic
approach. A careful examination of the inductive step above
DoubleDeckerTwice(n, x, y, z)
will reveal that it works when m − 1 ≥ 0 and 2m − 2 ≥ 0
if n > 0
(otherwise, bm−1 and a2m−2 are not defined). Therefore, we
then DoubleDecker(n, x, z, y)
need m > 0, so n0 = 0 is good enough, and we only need to
DoubleDecker(n, y, x, z)
verify that b0 = a0 .
The total number of moves for the above algorithm is So far, 4(2n −1) is our smallest number of moves for solving
therefore twice 2(2n − 1), which is 4(2n − 1). But can we the Double Decker Tower of Hanoi. As it turns out, we can
do better? One idea is to avoid fixing the order of the last two save one more move (and we later prove optimality)! This can
disks by forcing the correct order in the first place. Here’s a be done by adjusting the previous attempt not to recursively
first bad attempt. handle the two bottom disks (but only disks 2n − 1 and 2n):
DoubleDeckerBad(n, x, y, z) DoubleDeckerBest(n, x, y, z)
if n > 0 if n > 0
then DoubleDeckerBad(n − 1, x, y, z) then DoubleDecker(n − 1, x, y, z)
Move(1, x, y) Move(1, x, y)
DoubleDeckerBad(n − 1, z, x, y) DoubleDecker(n − 1, z, x, y)
Move(1, x, z) Move(1, x, z)
DoubleDeckerBad(n − 1, y, z, x) DoubleDecker(n − 1, y, z, x)
Move(1, y, z) Move(1, y, z)
DoubleDeckerBad(n − 1, x, y, z) DoubleDecker(n − 1, x, y, z)
The DoubleDeckerBad algorithm is a simple disguise of Switching the order of equal size disks is not an issue now
the standard Tower of Hanoi algorithm for 2n disks, which since DoubleDecker is called an even number of times (namely
was presented as algorithm Hanoi in Section I. Observe that four times). The total number of moves is given by an =
in order to transfer 2n disks from peg x to peg z, we first 4 · 2(2n−1 − 1) + 3 = 4(2n − 1) − 1 when n > 0, and a0 = 0.
transfer 2n − 1 disks from peg x to peg y (recursively in the To prove the above is optimal, we observe that the other
first three lines following if n > 0), then move the top disk possible strategy is to move the largest disk to its destination
from peg x to peg z (in the subsequent fourth line), and finally from the intermediate peg (instead of the source peg).
transfer 2n − 1 disks from peg y to peg z (recursively in the DoubleDeckerAltBest(n, x, y, z)
last three lines). This is nothing but the standard sequence of if n > 1
moves for the 2n-disk Tower of Hanoi. then DoubleDecker(n − 1, x, y, z)
In fact, it is not hard to verify that the recurrence bn = Move(1, x, y)
4bn−1 + 3 of DoubleDeckerBad has the solution bn = 4n − 1 Move(1, x, y)
(same as Tower of Hanoi for 2n disks). However, an interesting DoubleDecker(n − 1, z, y, x)
take on this is to consider the following two recurrences: Move(1, y, z)
an = 2an−1 + 1 Hanoi Move(1, y, z)
bn = 4bn−1 + 3 DoubleDeckerBad DoubleDeckerAltBest(n − 1, x, y, z)
else Hanoi(2n, x, y, z)
and show by induction that bn = a2n . For instance, an
inductive step for n = m > n0 will be The above algorithm generates the recurrence an =
2(2n−1 − 1) + 2 + 2(2n−1 − 1) + 2 + an−1 = an−1 + 2n+1
bm = 4bm−1 + 3 = 4a2m−2 + 3
when n > 1, which can be shown by induction to have the
= 2(2a2m−2 + 1) + 1 = 2a2m−1 + 1 = a2m solution an = 4(2n − 1) − 1, thus proving that this is optimal.
 The Double Decker can be easily generalized to a k-Decker and the characteristic equation:
(k > 1) with an>0 = 2k(2n − 1) − 1 moves. A further
xk+1 = xk + 2x − 2
generalization of k-Decker in which there are ki disks of size
i is also suggested in [3]. It is not hard toPshow that, based By observing that r0 = 1 is a root, we can express the
n
on Fact 3, this generalization
Pn requires 2( i=1 ki 2n−i ) − 1 characteristic equation as follows:
moves if kn > 1, and i=1 ki 2n−i if kn = 1, which is equal
to 2k(2n − 1) − 1 when k1 = k2 = . . . = kn = k > 1, and (x − 1)(xk − 2) = 0
2n − 1 if k = 1. and thus the k + 1 (distinct) roots are r0 = 1, and rs+1 =
√k
2ei2πs/k for 0 ≤ s < k (the k th roots of 2), where eiθ =
III. M OVE O NE G ET S OME F REE cos θ + i sin θ. An example when k = 5 is shown in Figure 3.
In this variation, we can move the top k ∈ N or fewer disks
from a given peg to another simultaneously, and still consider
this to be one move. Hence the name Move One Get Some
(k − 1) Free. It is not hard to see that the optimal number of
moves can be achieved by (when n > 0)
an = min 2an−i + 1
0<i≤min{k,n}

= 2an−min{k,n} + 1 = 2amax{n−k,0} + 1
since an must be non-increasing in n and, therefore, it is
better to moves simultaneously as many disks as possible when
moving the largest to its destination. The above recurrence is √
Fig. 3. The kth roots of 2 when k = 5: r1 = 5 2, r2 , . . . , r5 ; and r0 = 1.
simply an = 2an−k + 1 when n ≥ k. As such, we can show Generated in part by WolframAlpha at [Link] [14].
that an = 2dn/ke − 1, which amounts to breaking the original
stack of disks into dn/ke virtual disks, each consists of k or Using the above information about the roots for a given
fewer disks. The algorithm for this variation is shown below: k, one can construct several interesting proofs by induction
(possibly involving the complex numbers). For instance, when
√
MoveOneGetSomeFree(n, x, y, z) k = 2 (Move
if n > 0 √ One Get One Free), we have r√0 = n
1, r1 =√ 2,
and r2 = − 2. Given the form an = c1 +c2 2 +c3 (− 2)n
then MoveOneGetSomeFree(n − k, x, z, y) with a0 = 0, a1 = 1, and a2 = 1, we obtain
Move(min{k, n}, x, z)
MoveOneGetSomeFree(n − k, y, x, z) a0 = c1 + c2 + c3 = 0
√ √
The proof that an = 2dn/ke − 1 is by (strong) induction for a1 = c1 + 2c2 − 2c3 = 1
n = m > n0 : a2 = c1 + 2c2 + 2c3 = 1
am = 2am−k + 1 = 2(2 d(m−k)/ke
− 1) + 1 √ √
and c1 = −1, c2 = (1 + 2)/2, c3 = (1 − 2)/2, and
√ √
= 2 · 2dm/k−1e − 1 = 2 · 2dm/ke−1 − 1 = 2dm/ke − 1 1 + 2√ n 1 − 2 √ n
an = −1 + 2 + (− 2)
2 2
Following the same line of thought from the previous section
about the choice of base cases, we must ensure that we verify Therefore, one could try to prove by induction the following
enough, but not too many. The inductive step requires that for n ≥ 0:
am−k be defined and thus m ≥ k. So n0 = k − 1, which √ √
dn/2e 1 + 2√ n 1 − 2 √ n
means that we must verify all bases cases for n = 0, . . . , k−1. 2 = 2 + (− 2)
2 2
a0 = 2d0/ke − 1 = 1 − 1 = 0 which provides an√interesting and not so trivial interplay of
√ the
n
patterns 2d e and 2, but rather intuitive because 2n/2 = 2 .
an = 2dn/ke − 1 = 2 − 1 = 1, n = 1, . . . , k − 1 The proof (by strong induction) and the careful choice of base
case(s) follow, given n = m > n0 :
Therefore, the Move One Get Some (k −1) Free generalizes
the standard Tower of Hanoi (which becomes the special case
2dm/2e = 2d(m−2)/2+1e = 2 · 2d(m−2)/2e
when k = 1). Interestingly, we could also study this general
h 1 + √2 √ m−2 1 − √2 √
variation of the Tower of Hanoi by solving the recurrence an =
i
=2 2 + (− 2)m−2
2an−k + 1 itself, using the method of characteristic equations. 2 2
First, we transform the recurrence into a homogeneous one, h 1 + √2 √ m 1− 2
√
√ i
by subtracting (as outline in Section 1) an − an−1 = 2an−k − =2 2 + √ (− 2)m
4 2(− 2)2
2an−k−1 , which yields: √ √
1 + 2√ m 1 − 2 √ m
an = an−1 + 2an−k − 2an−k−1 = 2 + (− 2)
2 2
and since we must have m − 2 ≥ 0 in the inductive step, to role of disk 1 (the smallest). Finally, the rubber disk (still on
m > 1 = n0 so we must establish the base case for n = 0 top of the stack) is moved to its original peg. This explicitly
and n = 1 (which are both true). In general, one can prove in requires 1 + (2n+1 − 1) + 1 = 2n+1 + 1 moves (which can still
a similar way that the number of moves is be optimized because the first and last moves of the rubber
k−1 disk may be redundant, so to be exact, we have 2(2n − 1) − 1
and 2(2n − 1) + 1 moves for odd and even n, respectively).
X
2dn/ke − 1 = 2n/k cs ei2πns/k − 1
s=0 Since the above solution makes no use of k (in fact it treats
k as 0), then can we do better? Well, if k ≥ n − 1, then
for some appropriate values of c0 , . . . , ck−1 .
we can simply transfer the stack of n disks in 2n − 1 moves
Observe that 2dn/ke is infinitely faster than 2n , in fact the
with the standard Hanoi algorithm while keeping the rubber
ratio 2dn/ke /2n is asymptotically equal to 2−n(k−1)/k , which
disk in place at all times. Therefore, we must use k somehow,
approaches 0 for large n (and a fixed k). By choosing k ≈
and the optimal number of moves will vary asymptotically in
n/ log2 f (n), where 1 < f (n) ≤ 2n , the number of moves
[2n , 2 · 2n ].
for this version of the Tower of Hanoi grows asymptotically
We first present a non-optimal algorithm that guarantees an
as f (n). 1
asymptotic (2 − 2α−1 )2n number of moves, where 0 < α =
Finally, one interesting aspect of this variation is that the
n − k ≤ n. To keep the illustration simple, we assume that
number of optimal solutions can be huge. If we denote this
the original stack of n disks will end up on some peg and
number by bn , for n disks, and let r = n mod k, then
the rubber disk on another (not necessarily its original peg).
min{k,n}
X As this can be fixed by at most two additional moves, 2 the
bn = 1 + b2n−i asymptotic behavior is preserved. In addition, we use n as an
i=r+1+k·0r argument within the recursive function RubberDiskInTheWay,
Therefore, bn = 1 iff n mod k = 0. If n mod k = k − 1 6= 0, as well as a global parameter (in Forward).
then bn = 1 + b2n−k (and bk−1 = 1), so this generates the RubberDiskInTheWay(n, x, y, z)
sequence 1, 2, 5, 26, 677, 458330, . . . for n ≡ k−1, e.g. for odd if n > k
n when k = 2, which can be shown to grow asymptotically then Hanoi(k, x, z, y)
(n+1)/k
as (1.225902 . . .)2 ([Link] [10]). (y, z) ←Forward(k + 1, x, y, z)
Move(1, x, z)
IV. RUBBER D ISK IN T HE WAY (x, y) ←Backward(n − 1, x, y, z)
In this variation, and in addition to the stack of n disks, Hanoi(k, y, x, z)
there is a rubber disk initially placed through one of the two else Hanoi(n, x, y, z)
other pegs as shown in Figure 4. The rubber disk is rubbery
and light so it can sit on any disk, but only disks 1, . . . , k
where k ∈ {0} ∪ N can appear above the rubber disk (when Forward(h, x, y, z)
k = 0 no disk can sit on top of the rubber disk). At any point if h < n
in time, however, all disks must represent a legitimate Tower then Move(1, x, z)
of Hanoi state, i.e. respecting proper placement of disk sizes Hanoi(h, y, x, z)
once the rubber disk has been ignored and taken out of the return Forward(h + 1, x, z, y)
picture. The goal of this variation, called Rubber Disk in The return (y, z)
Way, is to transfer the entire stack of disks to another peg and
end up with the rubber disk on its original peg (with nothing
on top or below). Backward(h, x, y, z)
if h > k
then Hanoi(h, y, z, x)
Move(1, y, z)
return Backward(h − 1, y, x, z)
return (x, y)
The algorithm above works by first placing the top k disks
on the rubber disk (first call to Hanoi in RubberDiskInThe-
Way) to make a stack of height k + 1, then gradually grow the
Fig. 4. Rubber disk in the way, n = 4 height of that stack to n (using Forward) until disk n is free
to move. After moving disk n, we gradually shrink the height
It is not immediately obvious how one could benefit from of the stack from n down to k + 1 (using Backward) to pile
placing a disk on top of the rubber disk (e.g. when k > 0). For up the n − k largest disks (thus moving n − k − 1 disks on top
instance, a trivial solution, though not optimal since it ignores of disk n). Finally, we transfer the k disks that sit above the
k, is to first move the rubber disk on top of the initial stack of 2 An initial move of the rubber disk to the other empty peg will produce the
height n, then treat the resulting problem as one instance of symmetric solution. In addition, one last move of the rubber disk can ensure
Tower of Hanoi with n + 1 disks, where the rubber disk plays its proper positioning.
rubber disk (second call of Hanoi in RubberDiskInTheWay), disks on top of rubber disk). This entity represents the smallest
leaving the rubber disk free. disk in a Tower of Hanoi instance with n − k + 1 disks, where
It is easy to see that RubberDiskInTheWay contributes this smallest disk requires 1 + (2k − 1) = 2k moves to move
asymptotically 2 · 2k moves through its two calls to Hanoi, once. By Fact 3, it is then easy to see that the total number
and of moves is asymptotically 2k (2n−k ) + 2n−k = 2n + 2n−k ,
since the smallest disk must move 2n−k times. Therefore, the
[1 + (2k+1 − 1)] + [1 + (2k+2 − 1)] + . . . + [1 + (2n−1 − 1)] k
optimal number of moves is asymptotically (2 − 2 2−1 n
k )2 .

moves through each of the Froward and Backward algorithms, We end this section with a funny recursive algorithm for the
resulting in a total of Rubber Disk in The Way variation, for the sake of illustrating
how a “seemingly good” solution might not work out nicely
2(2k + 2k+1 + . . . + 2n−1 ) = 2k+1 + 2k+2 + . . . + 2n after all:
moves (asymptotically). Perhaps one of the famous proofs by KeepMovingIt(n, x, y, z)
induction pertains to power series, so we can easily prove (by if n > 0
induction) our result stated earlier for n > k (recall α = n−k). then Move(1, y, z) (rubber)
 1  KeepMovingIt(n − 1, x, z, y)
2k+1 + . . . + 2n = 2 − α−1 2n
2 Move(1, z, y) (rubber)
The inductive step for n = m > n0 proceeds as follows: Move(1, x, z)
Move(1, y, x) (rubber)
2k+1 + . . . + 2m = (2k+1 + . . . + 2m−1 ) + 2m KeepMovingIt(n − 1, y, x, z)
 1  2m−1 Move(1, x, y) (rubber)
= 2 − m−1−k−1 2m−1 + 2m = 2m + 2m − m−1−k−1 =
2 2 There is a nice symmetry to the solution and, in addition,
m
2  1 
observe that by ignoring the rubber moves in the above
2 · 2m − m−k−1 = 2 − m−k−1 2m
2 2 description, the algorithm will be exactly that of a standard
Now let us articulate the base case. Since we had to isolate Tower of Hanoi. Unfortunately, the recurrence an = 2an−1 +5
one term in the above sum (namely 2m ), the inductive step is not as good. By changing the recurrence into a homogeneous
should work as long as the sum has at least that one term one (with the same technique used so far), we obtain an =
and, therefore, m must satisfy m ≥ k + 1. So m > k = n0 3an−1 − 2an−2 , with the characteristic equation x2 = 3x − 2,
and hence we must verify the base case for n = k. But since and r1 = 1 and r2 = 2 as the two distinct roots. Therefore,
the statement of the proven property requires n > k, such a we conclude that an = c1 + c2 2n . Now,
base case is not valid. How do we handle this subtlety? Well,
the inductive step still works if m > k + 1, so we could set a0 = c1 + c2 = 0
n0 = k + 1 and verify the base case for all n ≤ k + 1. But a1 = c1 + 2c2 = 1
since n > k, the base case for n = k + 1 is all we need, which
1
states that 2k+1 = (2 − 21−1 )2k+1 (true). a2 = c1 + 4c2 = 7
In light of the above discussion, when a condition like n > k
where a0 and a1 correspond to trivial solutions, and a2 is
is not stated explicitly, do we face an endless search for a base
obtained from the recurrence a2 = 2a1 + 5 = 7 (already an
case? The answer is, of course, “No” because one has to know
indication that our solution is not optimal). A common mistake
something about what is being proved. A statement such as
here is to use a0 and a1 to solve for c1 and c2 , and obtain
the above requires a condition for it to be true. On the other
an = 2n − 1 (as good as plain old Hanoi!). Indeed, a0 and
hand, if the truth of it cannot be established, then the failure
a1 cannot be used as the base to solve for c1 and c2 because
of the base case is exactly what we want.
a1 6= 2a0 + 5, a result of the solution not being optimal (the
One can interpret the solution presented above as wedging
same is true for a0 and a2 since a2 6= 3a1 −2a0 ). Therefore, we
the rubber disk en route in its “correct” relative position below
should use a1 and a2 instead, to obtain c1 = −5, c2 = 3, and
the top k and above the remaining n − k disks. Therefore,
an = 3·2n −5 (and observe that this does not satisfy a0 ). This
we seem to be solving for a setting in which disk k + 1 was
is outside the asymptotic range [2n , 2 · 2n ], as expected. The
magically pulled away from the stack and placed on a separate
sequence an≥1 mod 10 cycles through 1, 7, 9, and 3 (same
peg, and must remain there after the transfer. Intuitively,
as DoubleDecker but shifted), which can be easily proved by
pulling the smallest disk away does not affect the asymptotic
induction (Hanoi cycles through 1, 3, 7, and 5).
number of moves, while pulling the largest disk away reduces
that asymptotic number by half (with the general number of
moves being anywhere between the two bounds). V. E XPLODING T OWER OF H ANOI
However, the algorithm still does not benefit from the fact We now consider an Exploding Tower of Hanoi. In this
that the rubber disk itself can be placed anywhere. Therefore, variation, if the largest remaining disk becomes free with
we can do even better! In fact, the optimal solution is not that nothing on top, it explodes and disappears. The goal is to
hard to conceive. The trick is to virtually consider the rubber make the whole tower disappear. For instance, an = 0 when
disk and the smallest k disks as one entity (which can assume n ≤ 1 (with either no disks or one free disk). With two disks,
two configurations, either rubber disk on top of k disks, or k once the smallest is moved, the largest disk becomes free and
explodes, so the smallest, being now the largest remaining free Iterating an≥0 produces the following integer sequence
disk, will follow, resulting in a2 = 1. Similarly, it is not hard 0, 0, 1, 2, 5, 10, 21, 42, 85, 170, . . . ([Link]
to see that a3 = 2. The optimal solution can be derived as [10]), with an = 2an−1 if n is odd, and an = 2an−1 + 1 if n
follows: To free the largest disk, one must move the second is even (and n > 0). This property can be proved by induction
largest, which as illustrated for the case of n = 2, will also using the recurrence we derived earlier. The inductive step
explode. Observe that no disks can explode prior to the largest. for n = m > n0 works as follows:
Therefore, we first transfer n−2 disks to some peg, then move
the second largest disk to another, hence freeing two disks for am = 2am−1 + am−2 − 2am−3 = 2am−1 + [am−2 − 2am−3 ]
two explosions at once, and finally repeat the solution for the which is 2am−1 + 0 if m − 2 (and m) is odd, and 2am−1 + 1
remaining n − 2 disks. if m − 2 (and m) is even. Since the inductive step requires
Exploding(n, x, y, z) that m − 3 ≥ 0, i.e. m > 2 = n0 , we must verify the base
if n > 1 case for n = 1 and n = 2, which are both true since a1 = 2a0
then Hanoi(n − 2, x, z, y) and a2 = 2a1 + 1.
Move(1, x, z) The above property means that an≥1 is the nth non-negative
disks n and n − 1 explode integer for which the binary representation consists of alter-
Exploding(n − 2, y, x, z) nating bits. Therefore, when n ≥ 2, this alternation starts with
1 and has exactly n − 1 bits, making it super easy to write
Given this algorithm, we establish the recurrence: down an in binary (for Hanoi, an consists of n bits that are all
1s). 3 This is another nice candidate for a proof by induction,
an = an−2 + 2n−2
for n = m > n0 :
and change it into a homogeneous one by annihilation of 2n−2 The number am−1 has m − 2 alternating bits starting with
as follows: 1. If m is odd (so is m − 2), then am−1 has an odd number
an = an−2 + 2n−2 of bits thus ending with 1, and am = 2am−1 shifts the bits of
am−1 and adds 0. If m is even (so is m−2), then am−1 has an
2 · an−1 = 2 · an−3 + 2 · 2n−3 even number of bits thus ending with 0, and am = 2am−1 + 1
shifts the bits of am and adds 1. In both cases, am has m − 1
an − 2an−1 = an−2 − 2an−3
alternating bits starting with 1.
to finally obtain an = 2an−1 + an−2 − 2an−3 and the The working of this inductive step relies on am−1 having
characteristic equation x3 = 2x2 + x − 2. By observing that at least one 1 bit in its binary representation; therefore, we
r1 = 1 is a root, we express the characteristic equation as need m − 2 ≥ 1 or m > 2 = n0 . This means n = 2 must be
(x − 1)(x2 − x − 2) = 0 and solve the quadratic equation for our base case and, indeed, a2 = 1 has an alternating pattern
the other two roots. The three distinct roots will be r1 = 1, of 2 − 1 = 1 bit starting with 1.
r2 = −1, and r3 = 2. Therefore, an = c1 + c2 (−1)n + c3 2n , Finally, it is worth noting here that this is one of the few
and since Tower of Hanoi variations where the optimal number of moves
a0 = c1 + c2 + c3 = 0 can be even (an≥1 mod 10 cycles through 0, 1, 2, and 5).

a1 = c1 − c2 − 2c3 = 0
VI. T HE P IVOT
a2 = c1 + c2 + 4c3 = 1 In this variation, called the Pivot Tower of Hanoi, only two
types of moves will be allowed. Either the smallest disk (disk
we have c1 = −1/2, c2 = 1/6, and c3 = 1/3. Finally,
1) is moved to any peg, or some disk and the smallest exchange
(−1)n + 2n+1 − 3 places (and this is considered to be one move). Therefore,
an =
6 except for the smallest disk, disks can only move by pivoting
So the Exploding Tower of Hanoi is asymptotically three around disk 1, hence the name of this variation. Of course,
times as fast as the Tower of Hanoi. An interesting aspect of we still require that, by pivoting, a disk cannot be placed on a
this solution, and more generally solutions to recurrences for smaller one. So, for instance, only the disk on top of a stack
integer sequences, is the ability to generate statements related can be exchanged with the smallest.
to divisibility that are suitable for proofs by induction. For It is not immediately clear why this variation can be solved.
instance, an immediate thought is to prove (by induction) that But it can, since every move of disk i 6= 1 to peg x can be
(−1)n + 2n+1 − 3 is a multiple of 6, as follows for n = m > emulated by moving disk 1 to peg x then making the exchange
n0 : with disk i, and in fact, the solution can be even faster than
the original Tower of Hanoi; the main focus will be on a proof
(−1)m + 2m+1 − 3 = (−1)m−2 + 4 · 2m−1 − 3 by induction.
First we observe that the optimal solution for the Tower of
= [(−1)m−2 + 2m−1 − 3] + 3 · 2m−1 = 6k + 6 · 2m−2 Hanoi is an alternating Hanoi sequence of moves in which
The above (strong) induction requires that 2m−2 is an integer 3 The recurrence a = a n−2 already suggests that a is either a
n n−2 + 2 n
so m − 2 ≥ 0, and thus m > 1 = n0 . So we must verify the sum of consecutive even powers of 2, or a sum of consecutive odd powers of
base case for n = 0 and n = 1, both of which are true. 2, hence the alternating bit pattern.
 Hanoi sequence equivalent to p1 , . . . , pk of length at most
(k − 2) + 2 = k.
Since the (strong) inductive step requires k − 2 ≥ 0 (the
length of the empty sequence), we must have k > 1 = l0 and
hence verify the base case for l = 0 and l = 1, which are both
true because the empty sequence (of length zero) is equivalent
to any alternating (Hanoi or Pivot) sequence of length l ≤ 1,
Fig. 5. Pivot Tower of Hanoi for n = 5, the disk on top of a stack can be in which only the smallest disk can move.
exchanged with the smallest. The equivalence of alternating sequences (we only need
H2P) implies that the first 2n − 2 moves (excluding the last
move of disk 1) in the optimal solution of the Tower of Hanoi
the smallest disk is involved in every other move. This can have an equivalent alternating sequence of moves for the Pivot
be seen from Fact 3: Since disk 1 makes 2n−1 moves, there Tower of Hanoi. Adding one last move of the smallest disk
are 2n−1 − 1 moves of the other disks (for a total of 2n − 1 positions it correctly on top of the stack for a total of at most
moves). With the solution being optimal, we never move the 2n − 1 moves. But how fast is the optimal solution for the
smallest disk twice in a row, so the 2n−1 moves of disk 1 Pivot Tower of Hanoi if we do not require the sequence of
must perfectly interleave the rest, and we have an alternating moves to be alternating (we have no choice but to alternate in
sequence of moves (starting with the smallest disk). Similarly, the Tower of Hanoi)?
an alternating Pivot sequence for the Pivot Tower of Hanoi A quick exploration reveals that, for the Pivot Tower of
is a sequence of moves that alternate between moving disk Hanoi, a0 = 0, a1 = 1, a2 = 3, a3 = 7 (so far matching the
1 (also the starting move) and pivoting a disk (exchanging it Tower of Hanoi), and a4 = 13 (as opposed to a4 = 15 for the
with disk 1). We will say that two alternating sequences are Tower of Hanoi). To gain some insight into the recurrence, an
equivalent if they result in the same placement of all disks, optimal solution must transfer the top n − 1 disks but without
except possibly for the smallest (disk 1). We are now ready placing the smallest on top of the stack, so that it can be
for a proof by induction for the following: used for pivoting to move the largest disk to its destination.
(H2P) Every alternating Hanoi sequence of length l has This maneuver results in a stack of n − 2 disks with disk 1
an equivalent alternating Pivot sequence of length at most l, separated from the stack, which implies that the solution for
and (P2H) every alternating Pivot sequence of length l has n − 1 disks needs to be repeated, except that the first move
an equivalent alternating Hanoi sequence of length at most l. is now provided for free! This suggests that the recurrence is
an = (an−1 − 1) + 1 + (an−1 − 1) = 2an−1 − 1. However,
An inductive step can proceed as follows for l = k > l0 : depending on the value of n, the separation of the smallest
(H2P) Given an alternating Hanoi sequence h1 , . . . , hk , disk might not place it on a favorable peg; for instance, disk
if hk is a move of disk 1, then consider the alternating 1 can end up sitting on top of disk n (with disks 2, . . . , n − 1
Pivot sequence equivalent to h1 , . . . , hk−1 ; this alternating forming a stack). So we require an extra move before we can
Pivot sequence of length at most k − 1 is also equivalent pivot disk n to its destination. But this will place disk 1 back
to h1 , . . . , hk (since the last move is for disk 1). If hk is on the same peg, so we require yet another extra move to carry
a move of disk i 6= 1 to peg x, then consider the alternating out the remainder of the solution. As it turns out for n ≥ 3,
Pivot sequence equivalent to h1 , . . . , hk−2 ; we can assume that an = 2an−1 − 1 when n is even, and an = 2an−1 − 1 + 2 =
this alternating Pivot sequence of length at most k − 2 ends 2an−1 + 1 when n is odd.
with pivoting, otherwise we can simply drop the last move
of disk 1 only to make the sequence even shorter. Therefore, Pivot(n, x, y, z, N oLstM v = False, F rstM vF ree = False)
we can extend p1 , . . . , pk−2 by first moving disk 1 to peg x, if n > 2
then exchanging disk i with disk 1 (pivoting), to produce an then Pivot(n − 1, x, z, y, True, F rstM vF ree)
alternating Pivot sequence equivalent to h1 , . . . , hk of length if n ≡ 1 (mod 2)
at most (k − 2) + 2 = k. then Move(1, x, z)
(P2H) Given an alternating Pivot sequence p1 , . . . , pk , if Exchange(n)
pk is a move of disk 1, then consider the alternating Hanoi if n ≡ 1 (mod 2)
sequence equivalent to p1 , . . . , pk−1 ; this alternating Hanoi then Move(1, x, z)
sequence of length at most k−1 is also equivalent to p1 , . . . , pk Pivot(n − 1, y, x, z, N oLstM v, True)
(since the last move is for disk 1). If pk is an exchange of if n = 2
disk i on peg x with disk 1 on peg y, then consider the then if not F rstM vF ree
alternating Hanoi sequence equivalent to p1 , . . . , pk−2 ; we can then Move(1, x, z)
assume that this alternating Hanoi sequence of length at most Exchange(n)
k − 2 ends with a move for some disk j 6= 1, otherwise we if not N oLstM v
can simply drop the last move of disk 1 only to make the then Move(1, x, z)
sequence even shorter. Therefore, we can extend h1 , . . . , hk−2 if n = 1
by first moving disk 1 to peg z (if it’s not already there), then then if not N oLstM v and not F rstM vF ree
moving disk i from peg x to peg y, to produce an alternating then Move(1, x, z)
 To annihilate the extra term in the non-homogeneous recur- first, then move the largest disk to its destination, and finally
rence, we find transfer n − 2 disks (recursively) on top of the largest; the
(n − 1)st disk will benefit from the free teleport between disks
an + an−1 = 2an−1 + 2an−2
n − 2 and n. Obviously, when n ≤ 2, no disk can benefit
to yield an = an−1 + 2an−2 and the characteristic equation from any teleport. The algorithm is shown below, and gives
x2 = x + 2 with roots r1 = 2 and r2 = −1. So an = the recurrence an = an−1 + an−2 + 1, for n > 2.
c1 2n + c2 (−1)n . Since our recurrence works for n ≥ 3, we BeamMeUpScotty(n, x, y, z)
now have: if n > 2
a2 = 4c1 + c2 = 3 then BeamMeUpScotty(n − 1, x, z, y)
a3 = 8c1 − c2 = 7 Move(1, x, z)
BeamMeUpScotty(n − 2, y, x, z)
with c1 = 5/6 and c2 = −1/3. Therefore, when n ≥ 2: disk n − 1 will be teleported
5 · 2n − 2(−1)n else Hanoi(n, x, y, z)
an =
6 Iterating an≥0 produces the integer sequence
So the Pivot Tower of Hanoi is asymptotically 6/5 times 0, 1, 3, 5, 9, 15, 25, 41, . . . that, starting with a1 , coincides
as fast as the Tower of Hanoi. It is worth noting here that the with Leonardo numbers ([Link] [10]). For
number of exchanges satisfy, for n ≥ 1, en = 2en−1 + 1, n > 0, we can show that an = 2Fn+1 − 1, by induction for
with e1 = 0; thus en = 2n−1 − 1 for n ≥ 1, which n = m > n0 :
means limn→∞ en /an = 3/5, so exchanges make about a
am = am−1 + am−2 + 1 = 2Fm − 1 + 2Fm−1 − 1 + 1
3/5 fraction of the total number of moves (as opposed to half
in the trivial alternating solution). = 2(Fm + Fm−1 ) − 1 = 2Fm+1 − 1
As in the previous section, the expression for an suggests
to prove by induction that 5 · 2n − 2(−1)n is a multiple of Since the recurrence is defined for n > 2, the above (strong)
6 when n ≥ 1. The inductive step for m > n0 proceeds as inductive step requires m > 2 (also m − 2 ≥ 0 so that am−1 ,
following: am−2 , and Fm−1 are all defined). Therefore, m > 2 = n0 ,
and the base case must be verified for n = 1 and n = 2.
5 · 2m − 2(−1)m = 5 · 4 · 2m−2 − 2(−1)m−2 Indeed, a1 = 1 = 2F2 − 1 and a2 = 3 = 2F 3 − 1.
= [5 · 2m−2 − 2(−1)m−2 ] + 15 · 2m−2 = 6k + 6 · 5 · 2m−3 Solving the recurrence an = an−1 + an−2 + 1 using an −
an−1 = an−1 − an−3 and the characteristic equation x3 =
For this strong induction we need 2m−3 to be an integer, so 2x2 − 1, which is (x − 1)(x2 − x − 1) = 0, will result in
m > 2 = n0 . Therefore, n = 1 and n = 2 must be verified as
2 h i
(and hence are) the base cases. an = √ φn+1 − (1 − φ)n+1 − 1
Finally, we observe that iterating an≥0 5
produces the following integer sequence: √ n > 0 and can also be proved by induction, where φ = (1+
for
0, 1, 3, 7, 13, 27, 53, 107, 213, 427, 853, 1707, . . . 5)/2 is the golden ratio (in fact this solution is exactly the
([Link] [10]). Therefore, starting with expression for 2Fn+1 − 1 obtained by solving the recurrence
n = 2, an mod 10 alternates between 3 and 7, and starting for Fibonacci numbers).
with n = 3, an mod 100 cycles through 7, 13, 27, and 53. Interestingly, one can easily show that the number of
These properties can also be proved by induction. teleports also satisfies the recurrence tn = tn−1 + tn−2 + 1
for n > 2 with t0 = t1 = t2 = 0, giving tn = Fn − 1
VII. B EAM M E U P S COTTY ! (T HE F IBONACCI T OWER ) for n > 0. Therefore, if we were to add the number of
For our last variation, we consider one called Beam Me moves and the number of teleports for n > 0 we obtain
Up Scotty, in which disk i for 1 < i < n is teleported for an + tn = 2Fn+1 − 1 + Fn − 1 = Fn+3 − 2.
free between the two disks i − 1 and i + 1, whenever the Another interesting observation is that the solution to this
former is sitting directly on top of the latter. 4 This seamless variation is infinitely faster (in the asymptotic sense) than the
teleport, which does not count among the moves, stands behind original Tower of Hanoi (a feature that is shared only with
the borrowed name of this variation from a phrase in popular Move One Get Some Free variation that can explicitly move
culture on Star Trek (even though captain James Kirk never multiple disks simultaneously).
√ This can be seen from the fact
really uttered that phrase) [6]. that an ≈ −1 + 2φn+1 / 5 for large n and that
The solution to this variation will relate the number of 2φn+1
moves in a Tower of Hanoi game to the Fibonacci numbers. lim √ =0
n→∞ 5 · 2n
As usual, we must (recursively) transfer the top n − 1 disks
It is worth noting here that if disk n is also allowed
4 We do not explicitly require that the teleported disk be on top of its stack; to be teleported under disk n − 1 whenever disk n − 1
however, this is surprisingly the only possible scenario: when disk i − 1 is makes a move, then an≥0 becomes shifted as follows:
placed on top of disk i + 1, the teleported disk i is either free to move (on top
of its stack), or sitting directly under disk i − 2; the latter case is impossible 0, 1, 1, 3, 5, 9, 15, 25, 41, . . .. This gives an = 2Fn − 1 (and
since disk i − 1 would have been first to teleport prior to its move. tn = tn−1 + tn−2 = Fn−1 ) for n > 0, which essentially
amounts to solving an instance of n − 1 disks as originally compared to the more research inclined type of problems,
defined for Beam Me Up Scotty, with one additional free and provide a framework to strengthen the understanding
teleport for the largest disk (disk n). This results in Fn+2 − 1 of recurrences and mathematical induction via a repetitive
for an + tn when n > 0. This modification preserves the and systematic treatment of the subject, while pointing out
asymptotic speed of Beam Me Up Scotty relative to the other how to avoid the pitfalls. We summarize below some of the
variations (it speedups it up by φ). Regardless, the asymptotic goals/highlights of the approach:
ratio of the
√ number of moves to the number of teleports is • Strengthen the general understanding of recurrences and
2φ = 1 + 5. proofs by induction.
• Provide a mechanism that teaches how to establish recur-
VIII. O N T HE S PEED OF T OWER OF H ANOI rences and think about them (and eventually solve them).
To appreciate of effect of an on the time needed to solve • Describe a systematic way to handle recurrences that is
a particular variant of the Tower of Hanoi, observe that it reasonable for introductory discrete mathematics.
will only take about 544 millenniums to solve Beam Me Up • Suggest ways to enrich the standard learning environment
Scotty with n = 64 disks, compared to the 585 billion years e.g. by asking for programming variations to a classically
for Tower of Hanoi with the same number of disks, a speedup known recursive algorithm.
of more than a million! But the Move One Get Some Free • Construct proofs by induction from the expressions ob-
remains the fastest, with a speedup of more than four billions tained for solutions to recurrences, and/or by solving a
when n = 64 and k = 2, thus taking about 146 years for recurrence in different ways and equating the results.
Move One Get One Free. • Highlight the pitfalls that are typically encountered in re-
Finally, and for the sake of pointing out a variation with currences (boundary conditions) and proofs by induction
an infinite slow down, consider the original Tower of Hanoi (base cases), e.g. by making a clear post-treatment of the
except that every move must involve the middle peg. This base cases in light of the inductive step.
variation is mentioned in [3]. Let the name of it be Man in • Create opportunities to have fun with the endless varia-
the Middle. A solution is presented below: tions of the Tower of Hanoi while learning the concepts.
ManInTheMiddle(n, x, y, z)
R EFERENCES
if n > 0
then ManInTheMiddle(n − 1, x, y, z) [1] T. Bousch. La tour de stockmeyer. Séminaire Lotharingien de
Combinatoire, 77:B77d, 2017.
Move(1, x, y) [2] T. Bousch et al. La quatrième tour de hanoı̈. Bulletin of the Belgian
ManInTheMiddle(n − 1, z, y, x) Mathematical Society-Simon Stevin, 21(5):895–912, 2014.
Move(1, y, z) [3] R. L. Graham, D. E. Knuth, O. Patashnik, and S. Liu. Concrete
mathematics: a foundation for computer science. Computers in Physics,
ManInTheMiddle(n − 1, x, y, z) 3(5):17–18, 1989.
[4] C. Grosu. A new lower bound for the towers of hanoi problem. arXiv
The recurrence generated by the above algorithm is an = preprint arXiv:1508.04272, 2015.
3an−1 + 2, which by inspection admits the solution an = [5] A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, and I. Stewart. The
3n − 1 (proof by induction), with an asymptotic relative time Tower of Hanoi-Myths and Maths. Springer, 2013.
[6] J. T. Kirk. (fictional character), star trek. The original series, 1966.
of (3/2)n (more than 1014 billion years for n = 64 disks). [7] U. Levy. Magnetic towers of hanoi and their optimal solutions. arXiv
Table 1 lists all variations in decreasing order of their preprint arXiv:1011.3843, 2010.
asymptotic time relative to Hanoi (from slowest to fastest). [8] É. Lucas. Récréations mathématiques, vol. iii, gauthier-villars, paris,
1893. Reprinted several times by Albert Blanchard, Paris.
Man in Middle k-Decker Rubber Disk Hanoi [9] G. S. Lueker. Some techniques for solving recurrences. ACM Computing
Surveys (CSUR), 12(4):419–436, 1980.
(3/2)n 2k 1 + 2−k 1
[10] N. J. A. Sloane. The on-line encyclopedia of integer sequences.
published electronically at https:// [Link], 2018.
1023 234 · 1010 117 · 1010 585 · 109
[11] P. K. Stockmeyer. Variations on the four-post tower of hanoi puzzle. In
k=2 k=0
Congress. Numer., volume 102, pages 3–12, 1994.
[12] P. K. Stockmeyer, C. Douglass Bateman, J. W. Clark, C. R. Eyster,
Pivot Exploding Beam Me Up Get k − 1 Free
2φ M. T. Harrison, N. A. Loehr, P. J. Rodriguez, and J. R. Simmons III.
5/6 1/3 √ (2/φ)−n 2−n(k−1)/k Exchanging disks in the tower of hanoi. International journal of
5
computer mathematics, 59(1-2):37–47, 1995.
488 · 109 195 · 109 544 · 103 146 [13] P. K. Stockmeyer and F. Lunnon. New variations on the tower of hanoi.
k=2 In Proc. of International Conference on Fibonaci Numbers and Their
Applications. Citeseer, 2008.
TABLE I
[14] Wolfram|Alpha. Wolfram Alpha LLC, https:// [Link]/
A SYMPTOTIC TIME RELATIVE TO H ANOI , AND APPROXIMATE REAL TIME
input/ ?i=r\%5E5\%3D2, 2018.
IN YEARS NEEDED TO TRANSFER n = 64 DISKS , ASSUMING ONE SECOND
PER MOVE .

IX. F INAL R EMARKS