The answer depends on the number of disks you need to move. In fact, we could answer the puzzle first for 1 disk, then 2, then 3 and so on. If we list out all of the answers for each number of disks, we will get a sequence of numbers. The \(n\)th term in the sequence is the answer to the question, “what is the smallest number of moves required to complete the Tower of Hanoi puzzle with \(n\) disks?” You might wonder why we would create such a sequence instead of just answering the question. By looking at how the sequence of numbers grows, we gain insight into the problem. It is easy to count the number of moves required for a small number of disks. We can then look for a pattern among the first few terms of the sequence. Hopefully this will suggest a method for finding the \(n\)th term of the sequence, which is the answer to our question. Of course we will also need to verify that our suspected pattern is correct, and that this correct pattern really does give us the \(n\)th term we think it does, but it is impossible to prove that your formula is correct without having a formula to start with.
in-context