The Tower of Hanoi game is very useful in understanding the Recurrence relation. It is a game of moving N disk between 3 needles. However, there are some rules we must follow before moving a disk from one needle to second needle.
Rule 1: Move only one disk at a time and it must be a top one.
Rule 2. Cannot move a larger disk on top of smaller one.
Rule 3: Number of moves should be minimum.
Let see how this works for 3 disk Tower of Hanoi game and using output of the game we can find solution to Tower of Hanoi game for N disk.
Let the total number of disk move be H.
If we want to compute total count for 4 disk Tower of Hanoi game.
= 2 . 7 + 1
= 14 + 1
There minimum 15 disk move required for 4 disk Tower of Hanoi game.
We can derive a much easier formula for Hn=2Hn + 1 + 1.
= 2n – 1
How we arrived at this solution, I leave it as an exercise for you.