When we analyzed the Towers of Hanoi algorithm, we counted the number of moves of individual rings, implicitly assuming that this operation takes constant time. Suppose instead that the time it takes to move a single ring is equal to the size of the ring, meaning that the ith$-$smallest ring takes i steps to move, for each $1<=$ i $<=$ n$.$ Write the resulting recurrence for the running time of the algorithm, and solve that recurrence. $(15$ points$)$

You can utilize the following identity in your analysis without giving a proof:

K

$$ i$2$i $=($K $1)2$K$+1+2.$

i$=1$