Some Local-Value Relationships for the Recurrence Relation Related to the Tower of Hanoi Problem
Some Local-Value Relationships for the Recurrence Relation Related to the Tower of Hanoi Problem
Keywords:
Tower of Hanoi, recurrence relation, local-value relationshipsAbstract
Motivated by the recurrence relation satisfied by the 4-peg tower of the Hanoi Problem, Matsuura [1] has considered the generalized recurrence relation of the form
{ }
1 t n
T(n, , ) min T(n t, , ) S(t,3) ,
= − +
where and are natural numbers, and S(t, 3) = 2t – 1 is the solution of the 3-peg Tower of Hanoi problem with t discs. This paper studies more closely the above recurrence relation and gives some new relationships, including some local-value relationships. The Reve’s puzzle is a particular case of the above recurrence relation with = 2.
References
Matsuura, A. Exact analysis of the recurrence relations generalized from the Towers of Hanoi. SIAM Proceedings in Applied Mathematics 129, 228 – 233 (2008).
Dudeney, H.E. The Canterbury Puzzles. Thomas Nelson and Son, London (1907) (4th ed. of 1919 published by Dover in 1958).
Majumdar, A.A.K. The Classical Tower of Hanoi Problem and Its Generalizations,Vol. 1: Multi-Peg Generalization. Lambert Academic Publishing, USA (2012).
