4
$\begingroup$

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?

  • 0
    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)$).2012-07-19

2 Answers 2

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$?).

1

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