Towers of Hanoi : Manipulative

I explained the directions and goal of the Towers of Hanoi to my girlfriend. We started from the beginning using two disks. She completed it with ease, so we moved on to 3 disks. She got it in one try, and told her to count the number of steps. We moved on to 4 disks and she started getting frustrated. After a few tries, I told her to focus on her moves and think about when there was only 2 and 3 disks. She said that she felt that there was a pattern but couldn't exactly see it. She ended up getting the 4 disks within 43 steps. She felt it was too long and I decided to tell her that it's only supposed to take 31 steps. We wrote down how many steps it took from 1 to 4 disks. She started to see the pattern and we figured out how many steps it would take all the way to 7 disks. This game is very helpful when analyzing patterns. While it can be frustating, it forces the person think in an enjoyable manner.