Derivación de la estimación asintótica (9.62) en Concrete Mathematics

Question

Estaba leyendo el capítulo 9: Asintótica en Graham, Knuth, Patashnik: Concrete Mathematics, y me quedé atascado mientras derivaba la siguiente estimación asintótica en la página 466: $$ \begin{equation} g_n = \frac{e^{\pi^2/6}}{n^2} + O(\log n / n^3) \, , \quad \text{for } n > 1 \, . \tag{9.62} \end{equation} $$ El valor $g_n$ es el coeficiente de $z^n$ en la función generadora $$ \begin{equation} G(z) = \exp\left(\sum_{k \geq 1} \frac{z^k}{k^2}\right) \, . \tag{9.57} \end{equation} $$

Para derivar la estimación, se empieza diferenciando $(9.57)$ : $$ G'(z) = \sum_{n \geq 0} n g_n z^{n-1} = \left( \sum_{k \geq 1} \frac{z^{k-1}}{k} \right) G(z) \, . $$ Igualación de los coeficientes de $z^{n-1}$ en ambos lados conduce a la siguiente recurrencia para $g_n$ : $$ \begin{equation} n g_n = \sum_{0 \leq k < n} \frac{g_k}{n-k} \, . \tag{9.58} \end{equation} $$ A continuación, se procede con el siguiente truco de bootstrapping. Empezar con una estimación inicial aproximada $g_n = O(1)$ obtenido demostrando que $0 < g_n \leq 1$ para $n \geq 0$ . Introduce la estimación inicial en la recurrencia para obtener una estimación mejor $g_n = O(\log n / n)$ . Introduciendo repetidamente nuevas estimaciones en la recurrencia y masajeando la recurrencia cuando es necesario, se obtienen estimaciones sucesivamente mejores, hasta llegar a la siguiente que está a un paso de $(9.62)$ (nótese el exponente colocado de forma diferente en el $O$ término): $$ \begin{equation} g_n = \frac{e^{\pi^2/6}}{n^2} + O(\log n / n)^3 \, , \quad \text{for } n > 1 \, . \tag{9.61} \end{equation} $$ Se supone que otro paso de bootstrapping da $(9.62)$ . Sin embargo, no consigo realizar el cálculo.

He aquí algunos de los intentos que hice.

Intento 1

Permítanme denotar la constante $e^{\pi^2 / 6}$ por $c$ . Cuando conecto $(9.61)$ directamente en $(9.58)$ Obtengo lo siguiente: $$ \begin{align} n g_n = {} & \frac{1}{n} + \sum_{0 < k < n} \frac{c}{k^2 (n-k)} + \sum_{0 < k < n} \frac{O(\log n)^3}{k^3 (n-k)} \\ = {} & \frac{1}{n} + c \sum_{0 < k < n} \left( \frac{1}{n k^2} + \frac{1}{n^2 k} + \frac{1}{n^2(n-k)} \right) \\ & {} + O(\log n)^3 \sum_{0 < k < n} \left( \frac{1}{n k^3} + \frac{1}{n^2 k^2} + \frac{1}{n^3 k} + \frac{1}{n^3 (n-k)} \right) \\ = {} & \frac{1}{n} + c \left( \frac{1}{n} H^{(2)}_{n-1} + \frac{2}{n^2} H_{n-1} \right) + O(\log n)^3 \left( \frac{1}{n} H^{(3)}_{n-1} + \frac{1}{n^2} H^{(2)}_{n-1} + \frac{2}{n^3} H_{n-1} \right) \, . \end{align} $$ (En el último paso, $H^{(i)}_{n-1}$ representa los números armónicos generalizados, y $H_{n-1}=H^{(1)}_{n-1}$ .) Esto parece ser peor que con lo que empecé, ya que por ejemplo $$ \frac{1}{n} H^{(3)}_{n-1} O(\log n)^3 = O\left( \frac{(\log n)^3}{n} \right) \, , $$ así que $O((\log n)^3 / n^2)$ aparece en la estimación final de $g_n$ .

Intento 2

Otro intento consiste en el truco de "sacar la parte más grande". Este truco se utiliza en Matemáticas Concretas para derivar $(9.61)$ . Podemos masajear la recurrencia $(9.58)$ para obtener lo siguiente: $$ \begin{align} n g_n & = \sum_{0 \leq k < n} \frac{g_k}{n} + \sum_{0 \leq k < n} g_k \left( \frac{1}{n-k} - \frac{1}{n} \right) \\ & = \frac{1}{n} \sum_{k \geq 0} g_k - \frac{1}{n} \sum_{k \geq n} g_k + \frac{1}{n} \sum_{0 \leq k < n} \frac{k g_k}{n-k} \, . \end{align} $$ La primera suma es $G(1)=c$ . Para la segunda suma, tengo $$ \begin{align} \sum_{k \geq n} g_k & = \sum_{k \geq n} \frac{c}{k^2} + O\left( \sum_{k \geq n} \frac{(\log k)^3}{k^3} \right) \\ & = c \left( \frac{\pi^2}{6} - H^{(2)}_{n-1} \right) + O\left( \frac{(\log n)^3}{n^2} \right) \, . \end{align} $$ No parece que vaya a acabar con algo tan bonito como $(9.62)$ pero al menos el error asintótico final sigue estando dentro de $O(\log n / n^3)$ . Sin embargo, las cosas vuelven a fallar cuando analizo la tercera suma: $$ \begin{align} \sum_{0 \leq k < n} \frac{k g_k}{n-k} & = \sum_{0 < k < n} \frac{c}{k (n-k)} + \sum_{0 < k < n} \frac{O(\log n)^3}{k^2 (n-k)} \\ & = \frac{c}{n} \sum_{0 < k < n} \left( \frac{1}{k} + \frac{1}{n-k} \right) + O(\log n)^3 \left( \frac{1}{n} H^{(2)}_{n-1} + \frac{2}{n^2} H_{n-1} \right) \\ & = \frac{2c}{n} H_{n-1} + O(\log n)^3 \left( \frac{1}{n} H^{(2)}_{n-1} + \frac{2}{n^2} H_{n-1} \right) \, . \end{align} $$ Al igual que en el intento 1, existe un término $$ \frac{1}{n} H^{(2)}_{n-1} O(\log n)^3 = O\left( \frac{(\log n)^3}{n} \right) \, , $$ que conduce a $O(\log n / n)^3$ en la estimación final de $g_n$ .

Intento 3

Después de sacar $1/n$ en el intento 2, vemos que la primera suma nos da exactamente el término principal en $(9.62)$ por lo que esa suma debería quedarse como está. La segunda y la tercera suma son problemáticas. Cada una por su cuenta contribuye demasiado, así que supongo que el truco está en fusionarlas de alguna manera. Una idea es intentar sacar otro $1/n$ de la tercera suma: $$ \sum_{0 \leq k < n} \frac{k g_k}{n - k} = \frac{1}{n} \sum_{0 \leq k < n} k g_k + \frac{1}{n} \sum_{0 \leq k < n} \frac{k^2 g_k}{n-k} \, . $$ Ahora la suma $\sum_{0 \leq k < n} k^2 g_k / (n-k)$ está bien: con el mismo tipo de análisis que en intentos anteriores concluimos que es $O((\log n)^4 / n)$ así que con todas las partes arrancadas contribuye $O(\log n / n)^4$ en la estimación final.

Qué hacer con $\sum_{0 \leq k < n} k g_k$ ? Mi idea era descomponerlo como en el intento 2: $$ \sum_{0 \leq k < n} k g_k = \sum_{k \geq 0} k g_k - \sum_{k \geq n} k g_k \, . $$ Desafortunadamente, esto no funciona, porque ahora la primera suma es $G'(1)$ y esto no converge.

¿Qué estoy haciendo mal? ¿Necesito masajear la recurrencia de alguna otra manera? Debe haber algo obvio que yo no veo.

Answer 1

Tenemos $\enspace\displaystyle n g_n = \frac{1}{n}\sum\limits_{k\ge 0}g_k - \frac{1}{n}\sum\limits_{k\ge n}g_k + \frac{1}{n}\sum\limits_{0<k<n}\frac{k}{n-k}g_k $

con $\enspace\displaystyle g_n = \frac{G(1)}{n^2} + O\left(\frac{\ln n}{n}\right)^3 \enspace$ y $\enspace\displaystyle G(1)=e^{\zeta(2)}\,$ .

Primera parte: $\enspace\displaystyle \sum\limits_{k\ge 0}g_k = G(1) $

Con $\enspace\displaystyle O\left(\frac{G(1)}{n^2} + O\left(\frac{\ln n}{n}\right)^3\right)= O\left(\frac{1}{n^2}\right)\enspace$ obtenemos

para la segunda parte $\enspace\displaystyle \sum\limits_{k\ge n}g_k = O\left(\sum\limits_{k\ge n}\frac{1}{k^2}\right)=O\left(\frac{1}{n}\right)\,$ ,

de dónde viene el último paso $\enspace\displaystyle \lim\limits_{n\to\infty}n^x\sum\limits_{k\ge n} \frac{1}{k^{1+x}}=\frac{1}{x}\enspace$ para $\enspace x>0\,$ .

La tercera parte es $\enspace\displaystyle \sum\limits_{0<k<n}\frac{k}{n-k}g_k = O\left(\sum\limits_{0<k<n}\frac{1}{k(n-k)}\right)=O\left(\frac{\ln n}{n}\right) \,$ .

Es lo que sigue: $\enspace\displaystyle g_n =\frac{1}{n}\left(\frac{G(1)}{n} - \frac{1}{n} O\left(\frac{1}{n}\right) + \frac{1}{n} O\left(\frac{\ln n}{n}\right)\right) = \frac{G(1)}{n^2} + O\left(\frac{\ln n}{n^3}\right)$