La suma $\sum\limits_{n \ge 0} \binom{m-1}{n} \frac{n!}{m^n} + \binom{n+1}{2}\binom{m-1}{n-1}\frac{(n-1)!}{m^n}$ es asintótica a $\sqrt{9m/8}$

Question

Consideremos la siguiente suma, conocida como la función Q de Ramanujan:

$$\begin{align} Q(m) &= 1 + \frac{m-1}{m} + \frac{(m-1)(m-2)}{m^2} + \cdots + \frac{(m-1)(m-2) \cdots 1}{m^{m-1}} \\ &= \sum_{n \ge 0} \binom{m-1}{n}\frac{n!}{m^n} = \sum_{n \ge 0} \frac{(m-1)!}{(m-n-1)! m^n} \end{align} $$

Surge en el estudio de los algoritmos de hashing y el problema del cumpleaños y está relacionado con (es menos por $1$ que) el tiempo previsto hasta la primera colisión.

Se sabe que tiene la expansión asintótica

$$Q(m) \sim \sqrt{\frac{\pi m}{2}} - \frac{1}{3} + \frac{1}{12}\sqrt{\frac{\pi}{2m}} - \frac{4}{135m} + \dots$$

y así podemos decir que

$$ \lim_{m\to\infty} \frac{Q(m)}{\sqrt{m}} = \sqrt{\frac{\pi}{2}}.$$

El papel "Sobre la función Q de Ramanujan" por Philippe Flajolet y otros da una prueba, y supongo que los métodos en las respuestas a esta pregunta funcionará.

Al analizar el tiempo previsto hasta la segundo colisión en una respuesta a otra pregunta aquí , se me ocurrió una suma similar que llamaré $Q_2(m)$ :

$$\begin{align} Q_2(m) &= 1 + \frac{m-1}{m} + \frac{(m-1)(m-2)}{m^2} + \frac{(m-1)(m-2)(m-3)}{m^3} + \dots \\ &\phantom{=1} + \frac{1}{m} + 3\frac{(m-1)}{m^2} + 6\frac{(m-1)(m-2)}{m^3} + \dots\\ &= \sum_{n \ge 0} \binom{m-1}{n} \frac{n!}{m^n} + \binom{n+1}{2}\binom{m-1}{n-1}\frac{(n-1)!}{m^n} \\ &= \sum_{n \ge 0} \left(\frac{(m-1)!}{(m-n-1)!} + \frac{(n+1)n (m-1)!}{2(m-n)!}\right) \frac1{m^n} \end{align} $$

Podemos demostrar que $Q(m) < Q_2(m) < 2Q(m)$ Así que $Q_2(m)$ también es asintóticamente del orden de $\sqrt{m}$ es decir, $\displaystyle \lim_{m \to \infty} \frac{Q_2(m)}{\sqrt{m}} = c$ para alguna constante $c$ satisfaciendo $\sqrt{\frac{\pi}{2}} < c < \sqrt{2\pi}$ .

Una evaluación informática de esta suma para un tamaño cada vez mayor $m$ (He probado los poderes de $2$ hasta $2^{38}$ ) dio los siguientes valores (de $Q_2'(m) = Q_2(m) + 1$ en realidad, pero eso no debería importar ya que ambos tendrán la misma asintótica):

log_2(m)      Q_2'(m) Q_2'(m)/sqrt(m)
      1      3.750000 2.651650
      2      4.828125 2.414062
      3      6.367527 2.251261
      4      8.556387 2.139097
      5     11.661068 2.061405
      6     16.058672 2.007334
      7     22.282951 1.969553
      8     31.089159 1.943072
      9     43.545730 1.924468
     10     61.163931 1.911373
     11     86.081225 1.902144
     12    121.320594 1.895634
     13    171.157295 1.891039
     14    241.637536 1.887793
     15    341.312003 1.885500
     16    482.273240 1.883880
     17    681.622711 1.882735
     18    963.545563 1.881925
     19   1362.244774 1.881353
     20   1926.090668 1.880948
     21   2723.489223 1.880662
     22   3851.181106 1.880460
     23   5445.978284 1.880316
     24   7701.362098 1.880215
     25  10890.956487 1.880144
     26  15401.724138 1.880093
     27  21780.912933 1.880058
     28  30802.448248 1.880032
     29  43560.825847 1.880014
     30  61603.896482 1.880002
     31  87120.651683 1.879993
     32 123206.792957 1.879986
     33 174240.303361 1.879982
     34 246412.585911 1.879979
     35 348479.606720 1.879977
     36 492824.171819 1.879975
     37 696958.213438 1.879974
     38 985647.343638 1.879973

Esto sugiere que la constante $c \approx 1.87997$ y, probando números de una forma similar a la $\sqrt{\frac{\pi}{2}}$ que tenemos para $Q(m)$ Me he dado cuenta de que $\sqrt{\frac{9\pi}{8}} = 1.8799712\dots$ .

Mis preguntas:

1. ¿Es cierto (podemos demostrar) que $$c = \lim_{m \to \infty} \frac{Q_2(m)}{\sqrt{m}} = \sqrt{\frac{9\pi}{8}}$$ ¿Exactamente?

2. Si no, ¿existe una forma cerrada para el límite $c$ ?

Answer 1

La asintótica que sugieres es correcta. Para ver esto, primero explicamos una aproximación elemental a la asintótica (ya conocida) de $$ Q(m)=\sum_{k=0}^{m-1}\prod_{i=1}^k\left(1-\frac{i}m\right). $$ Por cada $x$ , $1-x\leqslant\mathrm e^{-x}$ y la función $x\mapsto\mathrm e^{-x}$ es decreciente, por lo que $$ Q(m)\leqslant\sum_{k=0}^{m-1}\mathrm e^{-k(k+1)/(2m)}\leqslant1+\sum_{k=1}^{m-1}\int_{k-1}^k\mathrm e^{-x^2/(2m)}\mathrm dx, $$ que da como resultado $$ Q(m)\leqslant1+\int_{0}^{+\infty}\mathrm e^{-x^2/(2m)}\mathrm dx=1+\sqrt{\frac\pi2m}. $$ Asimismo, para cada $t$ en $[0,1)$ existe $c(t)$ tal que para cada $x$ en $[0,t]$ , $1-x\geqslant\mathrm e^{-c(t)x}$ . Se puede elegir $c(t)=-\frac1t\log(1-t)$ por lo que $c(t)\to1$ cuando $t\to0$ . Utilizando $t=m^{-1/4}$ y la abreviatura $C_m=c(m^{-1/4})$ se obtiene $$ Q(m)\geqslant\sum_{k=0}^{m^{3/4}}\prod_{i=1}^k\left(1-\frac{i}m\right)\geqslant\sum_{k=0}^{m^{3/4}}\mathrm e^{-C_mk(k+1)/(2m)}, $$ que da como resultado $$ \frac1{\sqrt{m}}Q(m)\geqslant\frac1{\sqrt{m}}\int_1^{m^{3/4}}\mathrm e^{-C_mx^2/(2m)}\mathrm dx=\frac1{\sqrt{C_m}}\int_{\sqrt{C_m/m}}^{m^{1/4}\sqrt{C_m}}\mathrm e^{-x^2/2}\mathrm dx. $$ Desde $C_m\to1$ , $\sqrt{C_m/m}\to0$ y $m^{1/4}\sqrt{C_m}\to\infty$ cuando $m\to\infty$ Esto da como resultado $$ \liminf\frac1{\sqrt{m}}Q(m)\geqslant\int_{0}^{+\infty}\mathrm e^{-x^2/2}\mathrm dx=\sqrt{\frac\pi2}. $$ La asintótica de $Q(m)$ sigue.

Resulta que cada paso de la prueba anterior puede adaptarse al caso de $$ Q'(m)=\frac1m\sum_{k=0}^{m-1}k(k+1)\prod_{i=1}^k\left(1-\frac{i}m\right). $$ Por ejemplo, $$ Q'(m)\leqslant\frac1m\sum_{k=0}^{m-1}k(k+1)\mathrm e^{-k(k+1)/(2m)}\leqslant\frac1m\sum_{k=1}^{m-1}\int_{k-1}^k(x+2)^2\mathrm e^{-x^2/(2m)}\mathrm dx, $$ así $$ Q'(m)\leqslant\frac1m\int_{0}^{+\infty}(x+2)^2\mathrm e^{-x^2/(2m)}\mathrm dx=\sqrt{m}\int_{0}^{+\infty}\left(x+\frac2{\sqrt{m}}\right)^2\mathrm e^{-x^2/2}\mathrm dx, $$ lo que es suficiente para demostrar que $$ Q'(m)\leqslant\sqrt{m}\int_{0}^{+\infty}\mathrm e^{-x^2/2}\mathrm dx+O(1)=\sqrt{\frac\pi2m}+O(1). $$ Asimismo, copiando la prueba de la cota inferior asintótica de $Q(m)$ se obtiene $$ \lim\frac1{\sqrt{m}}Q'(m)=\sqrt{\frac\pi2}. $$ Esto demuestra su afirmación ya que $Q_2(m)=Q(m)+\frac12Q'(m)$ .

De forma más general, aplicando la misma técnica a $$ Q^{(u)}(m)=\sum_{k=0}^{m-1}u(k)\prod_{i=1}^k\left(1-\frac{i}m\right), $$ donde $u(k)\sim ck^a$ con $a\geqslant0$ cuando $k\to\infty$ se obtiene $$ Q^{(u)}(m)\sim c2^{(a-1)/2}\Gamma\left(\frac{a+1}2\right)\cdot m^{(a+1)/2}. $$