Recursion Tower of Hanoi Consider the standard recursive solution to the Towers of Hanoi problem. In the traditional problem, all moves cost the same. Now, suppose the cost of a move is the size of the disk, with $1$ being the cost of the smallest disk, $2$ the second smallest, and so on. Express, as a recurrence relation, the cost of solving the $n$-disk problem.
Hey I don't understand this question at all since the traditional problem the cost would just be $(2^n - 1) \cdot cost$. But now we have to keep track of each disk which is unknown.

As the question asks you to simply write a recurrence relation for the cost, I am assuming it is for the original recursive solution. If instead you mean to at the same time minimize the cost, that could potentially be a different problem. The latter I have not considered in any detail.

Suppose $C(n)$ denotes the cost of solving it with $n$ discs. Then the $C(n+1)$ case goes as follows:


*

*We have the cost $C(n)$ of a sequence that will have to be performed twice

*Just add the cost of moving the $(n+1)$-th disc, and you are done


Writing out the details of this will establish a recurrence relation for $C(n+1)$ expressed in terms of $C(n)$ and some simple expression for the cost of the $(n+1)$-th disc. Can you take it from there?
