Towers of Hanoi recurrence relation 
How would I do this recurrence relation?
 A: 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?
A: 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
