`N =6`
No of moves is 45
Let the disks be numbered 1,…,`N_(1)`,…,N from smallest to largest. Without loss of generality (WLOG), suppose they are all on peg A at the start.
Disks N and `N_(−1)` are different colors, so at a minimum you must move disk `N_(−1)` off of disk N and onto another peg. WLOG, suppose you decide to move disk `N_(−1)` to peg B. In order to do that, you must first move disks `1,…,N_(−21),…,N_(−2 )` to peg C.
So now you have disk N on peg A, disk `N_(−1)` on peg B, and all the other disks on peg C. You have to get disk `N_(−2)` onto peg A. But in order to do this you have to move all the smaller disks from peg C to peg B . Do all of this, so now you have disks N and `N_(−2)` on peg A and all the other disks on peg B.
Fortunately, you do not have to move disk `N_(−3)` again, because it is already exactly where you want it (on top of disk `N_(−1)`). In fact, you now have the same problem you started out with, but with N−2 disks on peg B instead of N disks on peg A, and you need to move disk `N_(−3)` to peg A
we can make a recursive algorithm out of this, with the recursion occurring each time the number of disks to move is reduced by 2. Likewise, we can make a recursive formula to compute how many moves the algorithm will require.