Towers of Hanoi recurrence relation

Question

How would I do this recurrence relation?

Answer 1

Hint Let $a_n$ be the minimal number.

We try to find $a_{n+1}$ in terms of $a_n$. To move the $n+1$ disks, you need free the bottom disk. Thus, you need to move the top $n$ disks on one peg (how many moves), move next the bottom disk on the desired peg, and move the top $n$ disks on the top.

How many moves are there?

Answer 2

Let T(n) be the number of moves needed to transfer n disks from one peg to another.

Clearly we have:

T(0)=0

T(1)=1

Now, we note that in order to move a tower of n disks, we need to do the following:

Move the tower of n−1 disks from off the top of the nth disk onto another of the pegs; Move the nth disk to the destination peg; Move the tower of n−1 disks from where it was put temporarily onto the top of the nth disk. It is clear that steps 1 and 3 above each take Tn−1 moves, while step 2 takes one move.

Hence we have:

T(n)≤2T(n−1)+1 The inequality applies here because we have established that although we know we can always get the job done in no more than 2T(n−1)+1 moves, we are not at this stage certain that there is not a better strategy which needs fewer moves.

So: is there a way of moving the disks that uses fewer moves?

Consider that at some point we need to move disk n.

When we do this, we must have moved the n−1 disks above it onto a vacant peg. That must have taken T(n−1) moves to do, whatever T(n−1) happens to be.

Having moved that final disk for the first (and hopefully last) time[1], we then need to transfer the n−1 smaller disks (which all need to be on a single peg, otherwise there won't be a spare peg to move disk n onto) back onto disk n. This also takes T(n−1) moves to do.

So now we see that there is not a better way to move the disks, i.e.:

T(n)≥2T(n−1)+1

Thus we arrive at our recurrence rule:

T(n)=2T(n−1)+1