Birthday problem - Asymtotic of MEAN number of uniform draws before collision

Question

An experiment draws values uniformly at random among $k\ge1$, and stops when it is drawn a value identical to a previous one. The experiment's outcome $n$ is the number of draws before collision, an integer in range $[1,k]$.

What's a little-o expression for the mean outcome $\bar n$ as $k$ goes to infinity?

---

Probability of an outcome at least $n$ is $q_n=\displaystyle\prod_{j=0}^{n-1}{k-j\over k}\;=\;{k!\over(k-n)!\;k^n}$.

The Stirling approximation allows to derive $q_n\approx e^{-\frac{n^2}{2k}}$ for large $k$ and $n\ll k$. The median outcome is thus $o\left(2\sqrt{\log2}\,\sqrt k\right)$ with $2\sqrt{\log2}=1.1774\ldots$.

I get a mean outcome $\bar n=\displaystyle\sum_{0<i\le k}\frac{k!}{(k-i)!\,k^i}$ and from that numerical evidence $\bar n=o\left(\left(1.253\pm0.002\right)\sqrt k\,\right)$ but fail to derive the exact multiplicative constant.

Context is cryptography.

Answer 1

This looks like $\sqrt{\pi/2}$.
The terms have a logarithm that looks like the integral of minus $x$, so they have shape $exp(-x^2/2)$. Then summing them gives the integral from 0 to infinity.

Answer 2

Something equivalent is discussed in Philippe Flajolet & Andrew M. Odlyzko, Random Mapping Statistics, in proceedings of Eurocrypt 1989, and Research Report RR-1114, INRIA; 1989 (both open access).

Their theorem 3, (iii) tells that asymptotically, the expectation of tail + cycle length for iteration of a random function from and to a set of $k$ values is $\sqrt{k\pi/2}$ (equally split between tail and cycle). And, until looping in a cycle, the values reached by such iterated function are uniformly random, thus their statistic exactly matches our setting.

I'm still struggling at their proof, though.