Thanks for your helpful answer The Towers of Providence is a

Thanks for your helpful answer!

The Towers of Providence is a variation of the classical Towers of Hanoi problem. There are four pegs. denoted A. B. C. and D. and N disks of different sizes. Originally. all the disks are on peg A, stacked in decreasing size from bottom to top. Our goal is to transfer all the disks to peg D. and the rules are that we can only move one disk at a time. and no disk can be moved onto a smaller one. We can solve this problem with a recursive method: If N = 1, move this disk directly to peg D. and we are done. Otherwise (N > 1). perform the following steps: transfer the top N - 2 disks on peg A to peg B applying the method recursively: move the second largest disk from peg A to peg C: move the largest disk from peg A to peg D; move the send largest disk from peg C to peg D; transfer the N -2 disks on peg B to peg D applying the method recursively. Let T(N) be the total number of move; needed to transfer N disks. We have: T(1)= 1; T(N) = 2T(N - 2) + 3. Unfold this recurrence relation to obtain a closed-form expression for T(N). Assume that N is odd.

Solution

T(N) = 2T(N-2) + 3

therefore, T(N-2) = 2T(N-4)+3

Hence, T(N) = 2(2T(N-4) + 3) + 3

Therefore, T(N) = 2²*T(N-4) + 2*3+3

Similarly, T(N) = 2³T(N-6) + 3(1+2+2²)

.

.

T(N) = 2^(N-1)/2T(1) + 3(1 + 2 + 2² + ... + 2^(N-1)/2) [Assuming N is odd]

Therefore T(N) = 2^(N-1)/2 + 3*2^(N+1)/2 - 3

Therefore T(N) = 2^(N-1)/2 + 6*2^(N-1)/2

Therefore, T(N) = 7*2^(N-1)/2