I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my proof.
generalTH(n_disks,k_stacks)
if n<k:
### in 2n-1 moves reassemble ###
return
m = n-2
generalTH(n-m,k)
generalTH(m,k-1)
generalTH(n-m,k)
To solve towers of Hanoi, I know it takes the following number of moves: $$ T_k(n) = \begin{cases} 2^n-1, & k=3 \\ 2n-1, & n<k \\ 2T_k(n-m)+T_{k-1}(m), & n \geq k \end{cases} $$ Going through it - how can I show that the boundary case of $k=3$ can be within $\Theta(n)$?
Since $m = n-2$ : When I expand the recursion it seems easy to show that the first half is in $n$ - but I'm not sure how to show the boundary case will be in $n$? $$T_k(n)=2T_k(n-(n-2))+T_{k-1}(n-2)=2T_k(2)+2T_{k-1}(n-2-(n-4))+T_{k-2}(n-4)$$ $$...$$ $$T_k(n)\approx\Theta(2\cdot\lfloor\frac{k}{2}\rfloor)+\Theta(\text{boundary case})$$