I always like to answer these questions by approximating the difference equation with a differential equation (for which the result is always easier). In this case, the d.e. is $\dot x=-x^{1/k}$, $x(0)=n$, giving $t\approx \frac{k}{k-1}n^{(k-1)/k}$.