[Solved]: Solve recurrence relations

To make life simple, assume $T(1)=1$. If we look at this just for integral powers of $k$, i.e. $n=k^m$ for some $k in mathbb Z$, we have, by definition, $$ T(k^m)=kT(k^{m-1})+ckcdot k^m $$ We can repeatedly substitute into the recurrence to get: $$begin{align} T(k^m)&=kcdot{color{red}{T(k^{m-1})}}+ckcdot k^m &=kcdot{color{red}{[kcdot T(k^{m-2})+ckcdot k^{m-1}]}}+ckcdot k^m &= k^2cdot T(k^{m-2})+2ckcdot k^m &= k^3cdot T(k^{m-3})+3ckcdot k^m &= k^4cdot T(k^{m-4})+4ckcdot k^m end{align}$$ and in general we have $$ T(k^m) = k^jcdot T(k^{m-j})+jckcdot k^m $$ which could be formally proved by induction. The whole point of this iterative expansion, as it’s known, is to drive the $T(cdot)$ on the right side to a value we know, namely $T(1)$, so we’ll let $j=m$ to obtain $$ T(k^m) = k^mcdot T(k^0)+mckcdot k^m=k^mcdot T(1)+mckcdot k^m=k^m+mckcdot k^m $$ Finally, since we assumed that $n=k^m$, we have $m=log_kn$ and the expression above becomes: $$ T(n)=n+cknlog_k n=n(1+cklog_kn) $$ For the next part, presumably you’re being asked which of $k=2, 3, 4$ will make $T(cdot)$ smallest. For example, which is eventually smaller, $2log_2n$ or $3log_3n$? You should be able to answer this with a modicum of effort.