In how many steps the k peg version of the Towers of Hanoi Game can be solved?

In this we paper we consider the version of the classical Towers of Hanoi games where the game-board contains more than three pegs. For k pegs we give a 2 Ckn 1/(k−2) lower bound on the number of steps necessary for transferring n disks from one peg to another. Apart from the value of the constants Ck this bound is tight