Analysis of Recurrence Relations Generalized from the 4-Peg Tower of Hanoi

摘要

In this paper, we analyze recurrence relations generalized from the Tower of Hanoi problem of the form T(n,α,β) = min_(1≤1≤n){α T(n-t,α,β) +βS(t,3)}, where S(t, 3) = 2~t - 1 is the optimal total number of moves for the 3-peg Tower of Hanoi problem. It is shown that when α and β are natural numbers, the sequence of differences of T(n, α,β)'s, i.e., {T(n, α,β) - Tin - 1, α,β)}, consists of numbers of the formβ2~iα~j (i, j≥ 0) lined in the increasing order.