On generalized Frame–Stewart numbers

AbstractFor the multi-peg Tower of Hanoi problem with k≥4 pegs, so far the best solution is obtained by the Stewart’s algorithm in [15], based on the following recurrence relation: Sk(n)=min1≤t≤n{2⋅Sk(n−t)+Sk−1(t)},S3(n)=2n−1. In this paper, we generalize this recurrence relation to Gk(n)=min1≤t≤n{pk⋅Gk(n−t)+qk⋅Gk−1(t)},G3(n)=p3⋅G3(n−1)+q3, for two sequences of arbitrary positive integers (pi)i≥3 and (qi)i≥3 and we show that the sequence of differences (Gk(n)−Gk(n−1))n≥1 consists of numbers of the form (∏i=3kqi)⋅(∏i=3kpiαi), with αi≥0 for all i, arranged in nondecreasing order. We also apply this result to analyze recurrence relations for the Tower of Hanoi problems on several graphs