Why does the Tower of Hanoi problem take $2^n - 1$ transfers to solve? According to http://en.wikipedia.org/wiki/Tower_of_Hanoi, the Tower of Hanoi requires $2^n-1$ transfers, where $n$ is the number of disks in the original tower, to solve based on recurrence relations.
Why is that? Intuitively, I almost feel that it takes a linear number of transfers since we must transfer all but the bottommost disc to the buffer before transferring the bottommost disc to the target tower.

supose you have 3 discs, $D_1,D_2,D_3$ and the $D_1$ is the little one, and $D_3$ is the bigger one, so you have to transfer $D_1$ to one tower and then you have to transfere $D_2$ to a different tower from the two others,  so you put $D_1$ above $D_2$ and now you move $D_3$ to an other tower, so you put $D_1$ in the tower where  $D_3$ was  and you move $D_2$ to the towe where is $D_3$ , so you move $D_1$ to above $D_3$.  In fact, if you need $k $ moves in one step with $n$ discs you will need $2k+1$ moves if you have $n+1$ discs, because you need $k$ to change the $n$ disc above the bigger one, you need one move to change the bigger one, and you need again $k$ moves to change the $n$ discs again above the bigger disc.
