Self Similarities of the Tower of Hanoi Graphs and a proof of the Frame-Stewart Conjecture

Abstract

Considering the symmetries and self similarity properties of the corresponding labeled graphs, it is shown that the minimal number of moves in the Tower of Hanoi game with $p=4$ pegs and $n\ge p$ disks satisfies the recursive formula $F(p,n)={\min }_{1\le i\le n-1}\{2F(p,i)+F(p-1,n-i)\}$ which proves the strong Frame-Stewart conjecture for the case $p=4$. The method can be generalized to $p>4$.