Proof of $\sqrt{\pi/2}$ in birthday paradox? I had found in the past a publication in a crypto conference (in 80s if i am not mistaken) which I believe was the first proof why for example a random function $f:X\rightarrow X$ with $\#X=2^n,$ is expected to have collision in $\sqrt{\frac{\pi}{2}\times 2^n}$ iterations. I can't find it, anyone has the reference?
The paper you are looking for is:

"Random Mapping Statistics" by Flajolet and Odlyzko, first published in  Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434.

It is freely available via SpringerLink and via Archives-Ouvertes (PDF).

The relevant statistic you are looking for is probably the rho-length, which specifies the specifies the average length of a cycle to be $\sqrt{\pi n/2}$ where $n=2^k$ in your case.

The abstract reads as:


  Random mappings from a finite set into itself are either a heuristic
  or an exact model for a variety of applications in random number
  generation, computational number theory, cryptography, and the
  analysis of algorithms at large. This paper introduces a general
  framework in which the analysis of about twenty characteristic
  parameters of random mappings is carried out: These parameters are
  studied systematically through the use of generating functions and
  singularity analysis. In particular, an open problem of Knuth is
  solved, namely that of finding the expected diameter of a random
  mapping. The same approach is applicable to a larger class of discrete
  combinatorial models and possibilities of automated analysis using
  symbolic manipulation systems (“computer algebra”) are also briefly
  discussed.