Other towers of Hanoi
The tower of Hanoi is a classical puzzle in computer science that explores recursion, recurrences, and proofs by induction. A typical joke/fun fact among computer scientists is that if it takes one second to move a disk, then we need 585 billion years to finish the puzzle (compare this to an estimated age of the universe at 13.8 billion years)! So how can we make it faster (not necessarily much faster) while keeping it interesting? These are possible variants (all invented by the PI):

• Pivot: Either the smallest disk moves or some disk and the smallest exchange places.
• Exploding tower: If the largest disk remaining becomes free to move, it explodes. The goal is to make the tower disappear.
• Beam me up Scotty (from Startrek): If disk $i-1$ sits on top of disk $i+1$, disk $i$ is teleported for free (not a move).

The goal is to solve the puzzle optimally (with the minimum number of moves). Perhaps it would be most natural to start here by naming the number of moves $a_n$ (for a puzzle with $n$ disks), and constructing a mathematical recurrence in a way analogous to the standard Tower of Hanoi (there, $a_n=2a_{n-1}+1$ leads to the closed form solution $a_n=2^n-1$). Observe that the math in this case is almost synonymous to an algorithm (recurrence vs. recursion), so they both go hand-in-hand. Once the algorithm is implemented through recursion, observations about $a_n$ can be made for several reasonably small values of $n$. Now the program can inform the math, by suggesting a pattern for a closed form expression for $a_n$ that may be readily proved by induction (the natural mathematical tool for recurrences). However, when a closed form solution is hard to obtain, we can possibly use wolframalpha to derive those solutions from their corresponding recurrences. Another alternative is the use of oeis to look for the pattern of $a_n$ in existing known sequences. By relating the problem at hand to an existing one, we will be able to investigate further and relate the two solutions.

Extensions here are only limited by imagination, as one could always come up with new variants. This will give the satisfaction of formulating one's own research problems. In addition, several levels of difficulty can be explored; for instance, we may be initially asked for any solution to a puzzle, and not necessarily an optimal one.