Prueba $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$

Question

Más precisamente,

$$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$

Este es el Teorema 4 de Flajolet, Sedgewick (1995) y se ha obtenido a partir de Hankel de integración. Está relacionada con el análisis de quadtrees y digital de búsqueda de árboles.

Sé de Concreto de las Matemáticas' que de aspecto similar sumas pueden ser obtenidos y resuelto mediante la forma discreta de los derivados, $\nabla f(x)=f(x+1)-f(x)$ y por lo que $n^{\text{th}}$ diferencia es

$$\nabla^n f(x)=\sum_{k=0}^{n} \binom{n}{k} (-1)^{n-k} f(x+k) $$

y sé cómo usarlo para funciones simples como $f(x)=\dfrac1{x}$, pero no tengo idea de cómo resolver algo similar a la anterior.

Answer 1

Gracias a Andrés, J. M., y David Speyer! La siguiente solución se apoya fuertemente en lo que estas tres ya han publicado.

(En el interés de contar con una solución completa que he añadido el argumento de que obtiene de la OP suma a Andrew de la reformulación de la misma.)

---

Parte 1: Llegar a Andrew de la función gamma fórmula.

Ya que $$\int_0^1\sum_{m=1}^{k-1}\frac1{x+m}\, dx = \sum_{m=1}^{k-1}(\log(m+1) - \log m) = \log k,$$ podemos reescribir la fórmula original como $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k= \sum_{k=2}^n \binom{n}{k}(-1)^k\int_0^1\sum_{m=1}^{k-1}\frac1{x+m}\, dx = \int_0^1 \sum_{m=1}^{n-1} \frac1{x+m} \sum_{k=m+1}^n \binom{n}{k}(-1)^k\, dx.$$ Desde la alternancia de fila suma de los coeficientes binomiales son fáciles de evaluar (ver, por ejemplo, el Concreto de las Matemáticas, la Identidad 5.16), esto se convierte en (y, a continuación, cambiar el índice de vuelta a $k$) $$\int_0^1 \sum_{m=1}^{n-1} \frac1{x+m} (-1)^{m-1} \binom{n-1}{m}\, dx = \int_0^1 \sum _{k=1}^{n-1}\binom{n-1}{k} \frac{(-1)^{k-1}}{k+x} \, dx$$ $$ = \int_0^1 \left(\frac{1}{x} - \sum _{k=0}^{n-1}\binom{n-1}{k} \frac{(-1)^k}{k+x}\right) \, dx.$$ El resto de binomio de la suma de la realidad es parcial fracciones de la descomposición de $\frac{(n-1)!}{x(x+1)\cdots (x+n-1)}$. (Esta es la identidad 5.41 en Concreto de las Matemáticas. Desde otra perspectiva - también se trata en Concreto de las Matemáticas - el binomio de la suma es de $(-1)^n$ veces $n-1$ diferencia de $\frac{1}{x} = (x-1)^{\underline{-1}}$. La aplicación de la diferencia finita de la regla de los $\Delta x^{\underline{m}} = m x^{\underline{m-1}}$ sucesivamente $n-1$ veces por lo tanto, nos lleva a $\frac{(n-1)!}{x(x+1)\cdots (x+n-1)}$.)

Por lo tanto nuestra suma original es equivalente a $$\int_0^1 \left(\frac{1}{x} - \frac{(n-1)!}{x(x+1)\cdots (x+n-1)}\right) dx = \int_0^1 \left(\frac{1}{x} - \frac{\Gamma(n) \Gamma(x)}{\Gamma(n+x)}\right) dx,$$ cual es la formula de Andrew menciona en los comentarios.

---

Parte 2: la Reescritura de la expresión.

Ahora, reescribir así: $$\int_0^1 \left( \frac{1}{x} - \frac{\Gamma(n) \Gamma(x)}{\Gamma(n+x)} \right) dx = \int_0^1 \left( \frac{1}{x}\left(1- \frac{\Gamma(n) \Gamma(x+1)}{\Gamma(n+x)} \right)\right) dx.$$

Por $0 < x < 1$, $$\Gamma(x+1) = 1 - \gamma x + \frac{\zeta(2) + \gamma^2}{2}x^2 + O(x^3).$$ (Esta es la serie de Maclaurin para $\Gamma(x+1)$; ver la Expresión de 8.321 en Gradshteyn y Ryzhik. La única razón por la que esto es debido a que yo tenía que localizarlo para un artículo que escribí hace un par de años.) También, $$\frac{\Gamma(n)}{\Gamma(n+x)} = n^{-x}\left(1 + O\left(\frac{1}{n}\right)\right).$$ (Véase el DLMF.)

Poniendo todo esto significa que queremos que el valor asintótico de \begin{ecuación} \int_0^1 \frac{1-n^{-x}\left(1+ O\left(\frac{1}{n}\right)\right)\left(1 - \gamma x + \frac{\zeta(2) + \gamma^2}{2}x^2 + O(x^3)\right)}{x} dx. \etiqueta{1} \end{ecuación}

---

Parte 3: Obtención de la dominante términos.

Siguientes David Speyer y J. M., vamos a extraer lo que resulta ser la parte dominante de (1): $$\int_0^1 \frac{1-n^{-x}}{x}dx = \int_0^1 \frac{1-e^{-x \log n}}{x}dx = \int_0^{\log n} \frac{1-e^{-u}}{u} du = \text{Ein}(\log n),$$ donde $\text{Ein}(x)$ es el complementario integral exponencial. Ahora, $\text{Ein}(x) = E_1(x) + \log x + \gamma$, donde $E_1(x)$ es la habitual integral exponencial (de nuevo, ver la DLMF), y $E_1(x) < e^{-x} \log (1 + 1/x)$ (DLMF una vez más), por lo que poner todo esto junto nos han $$\int_0^1 \frac{(1-n^{-x})}{x}dx = \log \log n + \gamma + O\left(\frac{1}{n}\right).$$

---

Parte 4: la Obtención de los términos restantes.

Ahora consideramos el resto de (1). Este es $$\left(1+ O\left(\frac{1}{n}\right)\right)\int_0^1 n^{-x}\left(\gamma \frac{\zeta(2) + \gamma^2}{2}x + O(x^2)\right) dx$$ $$=\left(1+ O\left(\frac{1}{n}\right)\right)\left(\gamma \left(\frac{n-1}{n \log n}\right) - \frac{\zeta(2) + \gamma^2}{2}\left(\frac{n - \log n -1}{n (\log n)^2}\right) + O\left(\frac{1}{(\log n)^3}\right)\right)$$ $$a=\frac{\gamma }{\log n} - \frac{\zeta(2) + \gamma^2}{2(\log n)^2} + O\left(\frac{1}{(\log n)^3}\right),$$ que es el resto de la expresión solicitada por el OP.

Answer 2

Aquí no es riguroso enfoque que le da el derecho líder de fin de plazo dos primeros términos. Estoy escribiendo aquí con la esperanza de que alguien le de seguimiento y convertirlo en una prueba real. Este post es la CW, en el caso de que alguien quiera añadir a lo que he llegado con.

Voy a empezar con Andrew fórmula: $$\sum_{k=1}^n (-1)^k \binom{n}{k} \log k = \int_0^1 \left( \frac{1}{x} - \frac{\Gamma(n) \Gamma(x)}{\Gamma(n+x)} \right) dx = \int_0^1 \left( \frac{1}{x} - \frac{(n-1)!}{x(x+1)(x+2) \cdots (x+n-1)} \right) dx$$ $$=\int_0^1 \frac{dx}{x} \left( 1- \frac{1}{(1+x)(1+x/2) \cdots (1+x/(n-1))} \right)$$

Veamos que el denominador. $$\prod_{k=1}^{n-1} (1+x/k) = \exp \left( \sum_{k=1}^{n-1} \log \left(1+\frac{x}{k}\right) \right) \approx \exp \left( \sum_{k=1}^{n-1} \frac{x}{k} \right) \aprox e^{x \log n}.$$

Yo podría hacer que estas estimaciones más precisas, pero no me voy a molestar porque no tengo una rigurosa prueba. Así, a grandes rasgos, queremos calcular $$\int_0^1 \frac{1-e^{-x \log n}}{x} dx = \int_0^{\log n} \frac{1-e^{-u}}{u} du$$ donde hemos sustituido $u = x \log n$. Vamos a $[u>1]$ $1$ para $u>1$ y $0$ para $u<1$. Entonces podemos escribir esta integral como $$\int_0^{\log n} \frac{[u>1] du}{u} + \int_0^{\log n} \frac{1-[u>1]-e^{-u}}{u} du = \log \log n + \int_0^{\log n} \frac{1-[u>1]-e^{-u}}{u} du$$

Uno puede comprobar que la integral $\int_0^{\infty} (1-[u>1]-e^{-u})/u \ du$ converge a una constante $\gamma$, como JM señala a continuación. Por lo tanto, si podemos hacer que nuestras estimaciones precisas, este método dará $$\log \log n + \gamma + o(1) \quad \mbox {$n \to \infty$}.$$

"Concretas" que los métodos deben ser capaces de mejorar la aproximación $\sum_{k=1}^{n-1} \log \left(1+\frac{x}{k}\right) \aprox x \log n$ una buena oferta. Una vez que vemos lo que la versión mejorada parece, podemos tratar de averiguar qué hacer con el resto del argumento.