# Recurrence Relation for Towers of Hanoi

If you were to solve the Towers of Hanoi puzzle recursively by moving n - 1 smallest disks to the second rod, moving the largest disk, then recursively moving the stack from the second rod on top of the largest, you get the recurrence relation: $T(n) = 2T(n - 1) + 1$. So, let's say $S(n) = T(log_2n)$. How could I use this to write a recurrence relation for $S(n)$? As of right now I have: $$S(n) = 2T(log_2n - 1) + 1 = 2T(log_2n-log_22) + 1 = 2T(log_2(\frac{n}{2})) + 1$$ Not really sure if I'm going the right way with this, but I'm not sure where to go after this. After solving for a recurrence relation for $S(n)$, how could we use this to find an asymptotic expression for $T(n)$ using Big-O notation?

• $2T(\log_{2}(\frac{n}{2})) = 2S(\frac{n}{2})$ – Matija Sreckovic Jan 15 '18 at 18:51
• How did you get that? – A. L. Jan 15 '18 at 18:53
• If $S(n) = T(\log_{2}(n))$, then $S(\frac{n}{2}) = T(\log_{2}(\frac{n}{2}))$. – Matija Sreckovic Jan 15 '18 at 18:54
• So then the recurrence for $S(n)$ would be $S(n) = 2S(\frac{n}{2}) + 1$? And this would have a asymptotic complexity of $O(n)$? How could I use this to find a Big-O complexity for $T(n)$? – A. L. Jan 15 '18 at 19:13
• I'm not really good at proving $O$'s formally, but here's an intuitive approach: if you have a number $n$, and you want to keep dividing it by $2$ until you get $1$, you'll have to do it around $\log_{2}n$ times. So the asymptotic complexity of $S$ would be about $2 \times 2 \times 2... \times 2$, $\log_{2}n$ times, so it's about $2^{\log_{2}n} = n$ (if you ignore the $+1$'s). What happens to the $1$'s? Hint: how much is $1+2+...+2^k$? – Matija Sreckovic Jan 15 '18 at 19:33