# Find a closed sum: $\sum_{j=1}^{n}(j-1)\,2^{j-1}\,\left(\frac{k}{2}\right)^{\underline{j-1}}\,(k-j)^{\underline{n-j}}$

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?

-
It looks like a binomial expansion...without the combination coefficient, which means all of the middle terms would cancel and you would be left with the first and last term... Would also need to cancel the terms in the middle, but I'm guessing that's where the the "falling powers" comes in. –  david Oct 28 '12 at 15:04

Let's write $k=2 m$, since $k$ is assumed even: $$e_j = (j-1) 2^{j-1} \left(\frac{k}{2}\right)^{\underline{j-1}} (k-j)^{\underline{n-j}} = (j-1) 2^{j-1} m^{\underline{j-1}} (2m-j)^{\underline{n-j}}$$ The indefinite sum $\sum_j e_j$ can be computed using Gosper's algorithm, i.e. finding such a rational function $R(j)$ that: $$\sum_j e_j = R(j) e_j$$ or in other words, by solving: $$R(j+1) e_{j+1} - R(j) e_{j} = e_j$$ Bounding degrees of the numerator and the denominator of the rational function $R(j)$ it is easily guessed that $$R(j) = \frac{j-2k+1}{j-1}$$ fits the bill. Then $$\sum_{j=1}^n e_j = R(n+1) e_{n+1} - R_{1} e_1$$