The asymptotic behaviour of $\sum_{k=1}^{n} k \log k$.

Trying to simplify the following expressions in $n$ to ﬁnd its order of growth. I want to show the simplification separately from the order of growth

$$\sum_{k=1}^{n} k \log k = \Theta(n^2 \log n)$$

Any help with solving this one ? :( lost. Can someone break it down it stages please

-
–  Aryabhata Mar 19 '12 at 8:29
is there a good document to teach me this stuff ? –  ferron Mar 19 '12 at 8:32
That comment was intended for the future :-) Right now your problem is more basic :-) –  Aryabhata Mar 19 '12 at 8:33
It is in Aryabhata's link but note $\int x \; \log_e (x) \; dx = \frac12 x^2 \log_e(x) - \frac{x^2}{4} + c$ –  Henry Mar 19 '12 at 8:51

Note that $k\log k$ is an increasing function, i.e. as $k$ increases, so does $k \log k$. Also note that the terms are non-negative (we are talking $\log$ to base $2$).

So you can get an upper bound as follows:

$$\sum_{k=1}^{n} k \log k \le \sum_{k=1}^{n} n \log n = n^2 \log n$$

You can also get a lower bound by considering only the last $\frac{n}{2}$ terms. I will leave that to you as an exercise.

Next step would be to combine the two bounds to show that the sum is indeed $\theta(n^2\log n)$.

-
Of course this is true even if the base of the logarithms is not 2. –  Gerry Myerson Mar 19 '12 at 8:57
@GerryMyerson: Yes, as long as we pick the base to get $\gt 1$. –  Aryabhata Mar 19 '12 at 15:42
Can someone break it down it stages please

1. Find the important part.
2. Approximate the important part.
3. Show the important part behaves the way you want.
4. Show the unimportant part has a negligible contribution.
5. Double-check you've gotten all of the inequalities right.
6. Combine the information to prove the theorem.

To see Aryabhata's method in this light:

• To find an upper bound, he just took the whole sequence as the important part, and made a very crude approximation. This was good enough to get to step 6.
• To find a lower bound, he recognized two things:

• The very crude approximation to the whole sequence doesn't work, because the terms can be too small
• The final terms in the sequence are large

so, he took the last half as the important part, made the crude approximation, and again that was good enough to jump straight to part 6.

-

Using the Euler-Maclaurin Sum Formula yields the asymptotic expansion $$\sum_{k=1}^{n}k\log(k)=\frac12n^2\log(n)-\frac14n^2+\frac12n\log(n)+\frac{1}{12}\log(n)+O(1)$$

-

Note that

$\qquad \displaystyle \sum\limits_{i=1}^n iH_i = \frac{n(n+1)}{2}H_n - \frac{n(n-1)}{4}$

taken for instance from the TCS cheat sheet. With $H_n \sim \ln n$, this does what you want.

-