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} = 2{H_{n - 1}} + 1\;,\;\;\;\;\;\;\;\;\;Initial\;Condition\;{H_1} = 1\\\\ {H_n} = 2{H_{n - 1}} + 1\;,\;\;\;\;\;\;\;{H_1} = 1\\\\ {H_n} = 2\left( {2{H_{n - 2}} + 1} \right) + 1 = {2^2}{H_{n - 2}} + 2 + 1\\\\ {H_n} = {2^2}(2{H_{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}} + \ldots + 2 + 1\\\\ {H_n} = {2^{n - 1}} + {2^{n - 2}} + \ldots + 2 + 1 = {2^n} - 1\\\\ (Geometric\;\;Sum\;\;1 + 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).