Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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 $$

share|improve this answer
    
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. –  Ricbit Oct 29 '12 at 2:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.