Hello to everyone,

I have to find an optimal k for the following recurence:

T(n, 4) = 2^(n-k+1) + 2^k - 3

The above expression answers the question of how many moves, at least, are required for the problem of Hanoi with n disks and 4 towers to be solved. The problem was given to me as follows:

Given 4 towers and n disks, the n disks must go from tower A to tower D. First, I have to take n-k disks from A to B via C (cannot use D). Second, take k diskc from A to D via C (cannot use B). Finally, move n-k disks from B to D.

What I am most concerned about is an expression for the optimal k.

Can anyone help me please?

Tasos