Límite superior de la suma parcial $\sum k \lg k$ ¿a través de la suma?

Question

En esta conferencia de una clase de introducción a los algoritmos (vídeo ici (tiempo 74:09), el profesor cita lo siguiente como límite superior:

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

El profesor cita dos formas de ver la desigualdad: 1) "usando puramente sumas y hechos sobre sumas dividiendo la suma en dos partes y reconstituyéndola", y 2) usando una integral.

El método integral se puede resolver por integración por partes:

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

Intenté hacerlo por sumas, pero no estoy seguro de qué dividir. Se puede encontrar: $$\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}$$ que satisface el primer término del límite superior. Pero ¿cómo se obtiene el término cuadrado $(-n^2/8)$ por sumas?

Answer 1

En realidad, el límite dado es erróneo. La suma debería ser de $n-1$ no $n$ (Puedes comprobarlo mirando las notas de las conferencias asociadas al vídeo. Está en la diapositiva 42 ici ). Supongamos, para simplificar, que $n$ está en paz.

Tenemos $\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.$$

Utilizando la fórmula estándar $S(n)=\frac{n(n+1)}{2}$ , donde $S(n)$ es la suma del primer $n$ enteros positivos, este límite se evalúa como

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

Answer 2

Imagino que el método sería algo así: $$ \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 $$ y elija $m$ de forma óptima (posiblemente alrededor de $m=n/e$ ?).