Let H_n be the number of moves it takes to solve the tower of Hanoi with n disks. H_1 = 1 because if you have a tower with one disk you can clearly just move it where you want it.
Let's solve H_n for n>1 with a minimum of moves, tracking the largest disk. Let's call the spaces we can place disks on 1 (starting position) 2 (extra space) 3 (finishing space). First, to move the largest disk, we need to move the n-1 disks off of it. However, since the largest disk cannot be placed on any smaller disk, we also must have wherever we move it be completely free of disks. This means all n-1 disks must be on the space we're NOT moving the largest disk, and therefore by the rules of the game must be stacked as an n-1 tower itself. Therefore it takes a minimum of H_{n-1} moves just to get the large disk to another space. So this makes it clear that the minimal operation only moves the largest disk once, and therefore the minimum number of moves is always to 1.) move the first n-1 disks in H_{n-1} moves to space 2 2.) move the largest disk to space 3 3.) move the first n-1 disks in H_{n-1} moves to space 3. Therefore, H_n = 2 H_{n-1}+1. It then follows the sequence H_n is 1,3,7,... = 2^n-1
