Towers of Hanoi

When I was six I got a toy named "Towers of Hanoi". For those who don't know it: It consists of a plate with three staffs sticking in it and a few disks in different sizes. The task is to move all the disks one by one from one staff to another without putting a larger disk on a smaller one. After a few minutes of playing randomly without success I collected pencil and paper and started to solve the problem systematically. I carefully developed solutions for 1,2,3,4,5,6,... disks and always wrote down how many moves it took.

For one disk I needed one move of course, for 2 disks 3 moves, then 7, 15, 31, 63,... Because the number of moves raised so quickly I began to develop abbreviations for my solutions.

For example, if a subproblem was to move three disks from A to B and I already knew how to do that and I knew that it will take seven moves then why should I carry out the moves one by one? So I just moved the three disks simultaneously and counted this big move as seven elementary moves.

After hours of playing I got the enlightenment:
To move n disks from A to B I first had to move n-1 disks from A to C, then the largest disk from A to B and finally the n-1 disks from C to B. I was fascinated. This meant that I could solve the problem for ANY number of disks!
And I could compute the number of moves in advance! Without even carrying out a single move. The soltion was moves(n) = 2 * moves(n-1) + 1.
This was the day when my fascination for mathematics and informatics started.