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

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$.