Mathematical derivation of the multi-peg Tower of Hanoi algorithm

Abstract

A formal mathematical derivation is presented for the solution process of solving the multi-peg Tower of Hanoi puzzle, which consists of obtaining the minimum number of moves required to transfer the tower of n disks from the source peg to the destination peg, using any number of pegs such that each move transfers the topmost disk from one peg to another, in such a way that no larger disk is ever placed on top of a smaller one. It started with the well known recurrence relations and obtains a new formula for the problem of transferring n disks from the source peg to the destination peg using any number of pegs, t. The derivation explicitly makes use of the binomial coefficient and forward difference methods.

Keywords:

• Multi-peg tower of Hanoi
• binomial coefficient
• forward differences
• new algorithm