Recurrence relation complexity I just learned about recurrences and I just can't solve this problem. I have this recurrence relation:

$$
T(n) = \begin{cases}
k\cdot T(\frac{n}{k}) &amp; n &gt; 0\\
1 &amp; n = 0\\
\end{cases}
$$

where $k$ is a constant number.

I tried drawing a recurrence tree or replacing for lower $n$s but no success. I hope you can help me with an idea!
Suppose that $n$ is a power of $k$, say $n = k^t$. Then
$$
T(k^t) = kT(k^{t-1}) = k^2T(k^{t-2}) = \cdots = k^tT(1) = k^t,
$$
assuming a base case of $T(1) = 1$. So for powers of $k$, we have $T(n) = n$. You can also prove that by induction: if $T(n/k) = n/k$ then $T(n) = kT(n/k) = k(n/k) = n$.