What is the least number of moves needed to solve the k-peg Towers of Hanoi problem?

We prove that the solutions to the k -peg Tower of Hanoi problem given by Frame and Stewart are minimal. The proof relies on first identifying that for any n -disk, k -peg problem, there is at least one minimal sequence is symmetric. We show that if we order the number moved required for the disks in the minimal symmetric sequence in an increasing manner and obtain the sequence x i , then x i ≥ 2 i − 1 . We also prove that the maximum number of disks that can be moved using x i steps is k − 4 + i k − 3 . We use these to lower bound the telescopic sum (2) that is a lower bound on the number of moves required for any minimal symmetric sequence. This gives us the required result. [ABSTRACT FROM AUTHOR]