While analysing the run time of an algorithm, I used a counting argument to arrive at this expression:
$\sum_{j=1}^{n}(j-1)\,2^{j-1}\,\left(\frac{k}{2}\right)^{\underline{j-1}}\,(k-j)^{\underline{n-j}}=k^{\underline{n}} - 2^n\left(\frac{k}{2}\right)^{\underline{n}}$
This is valid whenever $k>n$ and $k$ is even. Powers with an underline are falling powers.
My question is: if I didn't know beforehand this closed sum, how could I find it?