Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$
If $n\lt k$, we have $T_k(n)=2n-1$. Let us focus on the remaining case, i.e, assuming $n\ge k$.
One of the recurrence relations is,
$$\quad  T_k(n) =6+T_{k-1}(n-2)\ \ \text{for all }n\ge k\ge\frac {n+3}2\text{ and }n\ge3, $$
where $6$ comes from $2T_k(2)$, since $T_k(2)=3$.
Applying the recurrence relation above repeatedly, we have
$$\begin{align}
T_k(n)&amp;=6\cdot 1+T_{k-1}(n-2\cdot1)\\
&amp;=6\cdot 2+T_{k-1}(n-2\cdot2)\\
&amp;=\cdots\\
&amp;=6\cdot (p-1)+T_{k-(p-1)}(n-2\cdot (p-1))\\
&amp;=6\cdot p+T_{k-p}(n-2\cdot p)\\
(\text{let us apply } T_k(n)=2n-1)\quad&amp;=6\cdot p+2(n-2\cdot p)-1\\
\end{align}$$
if we can choose $p$ such that

$n-2(p-1)\ge k-(p-1)\ge\dfrac{n-2(p-1)+3}2$,
which ensures all equalities except the last one hold, and
$n-2p&lt;k-p$,
which ensures the last equality holds.

Solving $p$ for those inequalities, we find that $p= n-k+1$.
$$T_k(n)=6\cdot p+2(n-2\cdot p)-1=4n-2k+1$$

So, we have
$$T_k(n) =\begin{cases}
  2n-1, &amp; n&lt;k \\
  4n-2k+1, &amp; n \geq k
\end{cases}$$
It is easy to check that $n\le T_k(n)&lt;4n$, so $T_k(n)=\Theta(n)$.

&quot;How can I show that the boundary case of $k=3$ can be within $\Theta(n)$?&quot;
What is the situation when $k=3$ under the assumption $k\ge\dfrac{n+3}2$? That means $n\le3$. So that situation is rather irrelevant since we are interested in the asymptotic behavior of $T_k(n)$.