1
$\begingroup$

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?

  • 0
    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.2012-10-28

1 Answers 1

2

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 $

  • 0
    Thanks! I always learn a lot from Math Stack Exchange :) Took me a while to understand your solution but now I got it. For me, however, the numerator of R(j) was j-2m-1 instead of j-2k+1. Also, R1e1 on the last equation has a division by zero, R2e2 gives the correct answer instead.2012-10-29