The Recursive Solution

This game becomes more interesting when we try to figure out the quickest solution to any Towers of Hanoi game. Most often the easiest way to wrap one's head around this is the recursive solution, for which we will use a simple proof by induction to prove that not only is any game of Towers of Hanoi solvable, but also that they all have a formulaic minimum number of moves to solution. We begin with the base case of a game that has only 1 disk. This is easy, you simply move to disk once to any other tower and the game is complete in only 1 move. There is in fact no way to not solve the game with a minimal number of moves with only 1 disk as the only possible 1st moves solve the game. So our base case is solvable, thus we have to now complete our inductive reasoning through a general case. For this step, we have a k disk game and we want to solve it under the assumption that we can solve a k-1 disk game. Well, this is simple, as we have 3 towers to work with. First, we solve the k-1 game, which we know we can solve by assumption, then we move the k^th (the largest of the disks) to the tower on which the other k-1 disks aren't on, then you solve the game by using the assumption that you can solve the k-1 game by moving the k-1 disks on top of the newly relocated k^th disk. We can see that this will always work as the induction holds.

[Show visualization of inductive solution][Hide visualization of inductive solution]