# The sum $\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}$ is asymptotic to $\sqrt{9πm/8}$

Consider the following sum, known as Ramanujan's Q-function:

\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}

It arises in the study of hashing algorithms and the birthday problem, and is related to (is less by $1$ than) the expected time until the first collision.

It is known to have the asymptotic expansion

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

and so we can say that

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

The paper "On Ramanujan's Q-function" by Philippe Flajolet et al, gives a proof, and I guess the methods at the answers to this question will work.

When analyzing the expected time until the second collision in an answer to another question here, I came up with a similar sum which I'll call $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}

We can prove that $Q(m) < Q_2(m) < 2Q(m)$, so $Q_2(m)$ is also asymptotically of the order of $\sqrt{m}$, i.e., $\displaystyle \lim_{m \to \infty} \frac{Q_2(m)}{\sqrt{m}} = c$ for some constant $c$ satisfying $\sqrt{\frac{\pi}{2}} < c < \sqrt{2\pi}$.

A computer evaluation of this sum for increasingly large $m$ (I tried powers of $2$ up to $2^{38}$) gave the following values (of $Q_2'(m) = Q_2(m) + 1$ actually, but that shouldn't matter as both will have the same asymptotics):

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


This suggests that the constant $c \approx 1.87997$, and, trying out numbers of a form similar to the $\sqrt{\frac{\pi}{2}}$ we have for $Q(m)$, I noticed that $\sqrt{\frac{9\pi}{8}} = 1.8799712\dots$.

My questions:

1. Is it true (can we prove) that $$c = \lim_{m \to \infty} \frac{Q_2(m)}{\sqrt{m}} = \sqrt{\frac{9\pi}{8}}$$ exactly?

2. If not, is there a closed form for the limit $c$?

The asymptotics you suggest is correct. To see this, we first explain an elementary approach to the (already known) asymptotics of $$Q(m)=\sum_{k=0}^{m-1}\prod_{i=1}^k\left(1-\frac{i}m\right).$$ For every $x$, $1-x\leqslant\mathrm e^{-x}$, and the function $x\mapsto\mathrm e^{-x}$ is decreasing, hence $$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,$$ which yields $$Q(m)\leqslant1+\int_{0}^{+\infty}\mathrm e^{-x^2/(2m)}\mathrm dx=1+\sqrt{\frac\pi2m}.$$ Likewise, for every $t$ in $[0,1)$ there exists $c(t)$ such that for every $x$ in $[0,t]$, $1-x\geqslant\mathrm e^{-c(t)x}$. One can choose $c(t)=-\frac1t\log(1-t)$ hence $c(t)\to1$ when $t\to0$. Using $t=m^{-1/4}$ and the shorthand $C_m=c(m^{-1/4})$, one gets $$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)},$$ which yields $$\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.$$ Since $C_m\to1$, $\sqrt{C_m/m}\to0$ and $m^{1/4}\sqrt{C_m}\to\infty$ when $m\to\infty$, this yields $$\liminf\frac1{\sqrt{m}}Q(m)\geqslant\int_{0}^{+\infty}\mathrm e^{-x^2/2}\mathrm dx=\sqrt{\frac\pi2}.$$ The asymptotics of $Q(m)$ follows.
It happens that every step of the proof above can be adapted to the case of $$Q'(m)=\frac1m\sum_{k=0}^{m-1}k(k+1)\prod_{i=1}^k\left(1-\frac{i}m\right).$$ For example, $$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,$$ thus $$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,$$ which is enough to show that $$Q'(m)\leqslant\sqrt{m}\int_{0}^{+\infty}\mathrm e^{-x^2/2}\mathrm dx+O(1)=\sqrt{\frac\pi2m}+O(1).$$ Likewise, copying the proof of the asymptotic lower bound of $Q(m)$, one gets $$\lim\frac1{\sqrt{m}}Q'(m)=\sqrt{\frac\pi2}.$$ This proves your claim since $Q_2(m)=Q(m)+\frac12Q'(m)$.
More generally, applying the same technique to $$Q^{(u)}(m)=\sum_{k=0}^{m-1}u(k)\prod_{i=1}^k\left(1-\frac{i}m\right),$$ where $u(k)\sim ck^a$ with $a\geqslant0$ when $k\to\infty$, one gets $$Q^{(u)}(m)\sim c2^{(a-1)/2}\Gamma\left(\frac{a+1}2\right)\cdot m^{(a+1)/2}.$$
• I'm having trouble with this part: "for every $t$ in $[0,1)$ there exists $c(t)$ such that for every $x$ in $[0,t]$, $1-x\geqslant\mathrm e^{-c(t)x}$" — I can follow it for $t \in [0, 1)$ as written, but later you take $t \to \infty$, so if I try to prove it for $t \in [0, \infty)$ instead, it's not so clear. (E.g. $x = 1$ would trip us up.) Could you help? – ShreevatsaR Jun 15 '13 at 14:27
• Interesting. This immediately gives that three collisions occur in less than an expected $2 \sqrt{\pi m/2} = \sqrt{2\pi m}$. (In fact, I will guess that it's $15/8 \sqrt{\pi m/2}$.) Since $\sqrt{2\pi m}$ is the square root of the circumference of a circle of radius $m$, there is clearly a geometric proof we're missing. :) – Fixee Jun 15 '13 at 15:58