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.

In this lecture of an introductory class to algorithms (video here, time 74:09), the professor cites the following as an upper bound:

$$ \sum_{k=2}^n k \lg k \leq \frac{1}{2} n^2 \lg n - \frac{1}{8} n^2.$$

The professor cites two ways of seeing the inequality: 1) by "using purely summations and facts about summations by splitting the summation into two pieces and reconstituting it", and 2) by using an integral.

The integral method can be solved by integration by parts:

$$ \sum_{k=2}^n k \lg k \leq \int_{2}^n x \lg x = \frac{1}{2} x^2 \lg x - \frac{1}{4\ln 2} x^2 < \frac{1}{2} n^2 \lg n - \frac{1}{8} n^2.$$

I tried doing it by sums, but am not sure what to split. One can find: $$\begin{align} \sum_{k=2}^n k \lg k &= 2 \lg 2 + 3 \lg 3 + \cdots + (n-1)\lg(n-1) \\ &\leq 2\lg(n-1) + 3\lg(n-1) + \cdots (n-1) \lg(n-1) \\ &\leq \lg(n-1) \sum_{k=2}^n k = \lg(n-1) \frac{n^2-n-2}{2}, \end{align}$$ which satisfies the first term in the upper bound. But how does one get the square term $(-n^2/8)$ by sums?

share|improve this question
    
The integral method you rely on is wrong: the integral should be on the interval $(2,n+1)$ and the value of the integral is not what you write (even if the integral is on $(2,n)$). –  Did Jul 19 '12 at 23:03

2 Answers 2

I imagine the method would be something like: $$ \sum_{k=2}^n k\lg k = \sum_{k=2}^m k\lg k + \sum_{k=m+1}^n k\lg k \le \frac{m^2-m-2}2 \lg m + \frac{n^2-2-m^2+m}2 \lg n $$ and choose $m$ optimally (possibly around $m=n/e$?).

share|improve this answer

The bound given is actually wrong. The sum should be to $n-1$, not $n$ (You can check this by looking at the lectures notes associated with the video. It's on slide 42 here). Assume for simplicity that $n$ is even.

We have $\lg n/2 \le \lg n -1$.

$$\sum_{k=2}^{n-1} k\lg k = \sum_{k=2}^{n/2} k\lg k + \sum_{k=n/2+1}^{n-1} k\lg k\le (\lg n -1)\sum_1^{n/2}k+\lg n\sum_{n/2}^{n-1} k.$$

Using the standard formula $S(n)=\frac{n(n+1)}{2}$, where $S(n)$ is the sum of the first $n$ positive integers, this bound evaluates to

$$\frac{n(n-1)}{2}\lg n-\frac{(n/2)(n/2+1)}{2}\le n^2\lg n-\frac{n^2}{8}.$$

share|improve this answer

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.