I’m trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=Theta(n)$ for all $kgeq 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)approxTheta(2cdotlfloorfrac{k}{2}rfloor)+Theta(text{boundary case})$$