The Tower Of Hanoi Puzzle

 The Tower Of Hanoi Puzzle (Nineteen Century)

There are 3 pegs . Initially the first peg has n disks that are placed in order of size.

Rule: Allow disks to be moved one at a time from one peg to another as long as a disk is never placed on top of a smaller one.

Goal: Move all disks to the other pegs.

Example: 

Let H_n denotes the number of moves needed to solve the Tower of Hanoi puzzle. 

Transfer the top n-1 disks. This can be done in H_n-1 steps. Transfer the largest disk (one step). Then transfer the (n-1) pegs on the largest disk (This can be 

done in H_n-1ways).

Thus  

$$\begin{array}{l}{H}_n=2H_{n-1}+1,InitialCondition{H}_1=1\\ \\ H_n=2H_{n-1}+1,H_1=1\\ \\ H_n=2\left(2H_{n-2}+1\right)+1=2^2{H}_{n-2}+2+1\\ \\ H_n=2^2(2H_{n-3}+1)+2+1=2^3{H}_{n-3}+2^2+2+1\\ \\ H_n=2^3{H}_{n-3}+2^2+2+1\\ .\\ .\\ .\\ H_n=2^{n-1}{H}_1+2^{n-2}+\dots +2+1\\ \\ H_n=2^{n-1}+2^{n-2}+\dots +2+1=2^n-1\\ \\ (GeometricSum1+p+p^2+...+p^{(n-1)}=(p^n-1)/(p-1))\end{array}$$

“ Monks want to transfer 64 gold disks from one peg to another according to rules of Hanoi Puzzle”

They need to perform 2⁶⁴-1 Steps we need about 500 billion years (If 1 move take a Second).