Find the number of terms of a product to make it 1/2 How to find $k$ such that:
$$\prod_{j=1}^{k-1} \Big(1 - \frac jn \Big) = \frac 12$$
?
According to a book I'm reading, this should hold approximatively when $k \approx \sqrt{n}$ (no proof is given).
Indeed, it seems to work. The equation is equivalent to
$$\begin{align}\sum_{j=1}^{k-1} \log\Big(1 - \frac jn \Big) = - \log(2)\end{align}$$
i.e.
$$\begin{align}\sum_{j=1}^{k-1} \Big( \frac {-j}n + O\Big(\frac {k^2}{n^2}\Big)  \Big) = - \log(2) \end{align}$$
or
$$\frac {1}{n}\begin{align}\sum_{j=1}^{k-1} j + O\Big(\frac {k^3}{n^2}\Big)  =  \log(2) \end{align}$$
Let's suppose $k^3 = o(n^2)$. Then
$$\frac 1 n \frac{k(k-1)}{2} + o(1) = \log(2)$$
and this proves that:
$$\frac{k^2}{n} + O\Big(\frac k n\Big) + o(1) = 2 \log(2)$$
This means that $k$ should be taken around $c \sqrt{n}$, with $c = \sqrt{2\log2}$.
This seems to work, but is there a cleaner proof that leads to a more precise result?

Application: If $k$ people choose a random number in $\{1, 2, \cdots, n \}$, then the probability of at least two people having chosen the same number (i.e. probability of a "collision") is $1/2$, when $k = c \sqrt{n}$.
See birthday problem.

Starting with
$\sum_{j=1}^{k-1} -\log\Big(1 - \frac jn \Big) 
=  \log(2)
$
we can use,
for $0< x <  1$,
$-\log(1-x)
=\sum_{m=1}^{\infty} \dfrac{x^m}{m}
$.
Then,
using the first $h$ terms,
$-\log(1-x)
\gt\sum_{m=1}^{h} \dfrac{x^m}{m}
$.
Looking at the remaining terms,
$\sum_{m=h+1}^{\infty} \dfrac{x^m}{m}
\lt \sum_{m=h+1}^{\infty} \dfrac{x^m}{h+1}
=\dfrac1{h+1} \sum_{m=h+1}^{\infty}x^m
=\dfrac{x^{h+1}}{(h+1)(1-x)}
$
so that
$-\log(1-x)
\lt\sum_{m=1}^{h} \dfrac{x^m}{m}+\dfrac{x^{h+1}}{(h+1)(1-x)}
$.
Setting $h=1$,
$x < -\log(1-x)
\lt x+\dfrac{x^{2}}{2(1-x)}
$.
Using the lower bound,
if $n > k$,
$\log(2)
\gt \sum_{j=1}^{k-1} j/n
=\dfrac{k(k-1)}{2n}
$.
Using the upper bound,
if $n > k$,
$\begin{array}\\
\log(2)
&\lt \sum_{j=1}^{k-1} (j/n+\dfrac{j^2/n^2}{2(1-j/n)})\\
&<\dfrac{k(k-1)}{2n}+\sum_{j=1}^{k-1}\dfrac{j^2/n^2}{2(1-k/n)}\\
&=\dfrac{k(k-1)}{2n}+\dfrac{1}{2n(n-k)}\sum_{j=1}^{k-1}j^2\\
&=\dfrac{k(k-1)}{2n}+\dfrac{1}{2n(n-k)}\dfrac{(k-1)k(2k-1)}{6}\\
&<\dfrac{k(k-1)}{2n}+\dfrac{(k-1)k^2}{3n(n-k)}\\
&=\dfrac{k(k-1)}{2n}(1+\dfrac{2k}{3(n-k)})\\
\end{array}
$
so that
$1
\lt \dfrac{2n\log(2)}{k(k-1)}
\lt 1+\dfrac{2k}{3(n-k)}
$.
From the first,
$n 
> \dfrac{k(k-1)}{2\log(2)}
> \dfrac{k(k-1)}{2}
$.
From the second,
$\dfrac{k}{n-k}
\lt \dfrac{k}{k(k-1)/2-k}
= \dfrac{1}{(k-1)/2-1}
= \dfrac{1}{(k-3)/2}
= \dfrac{2}{k-3}
$
so
$ \dfrac{2n\log(2)}{k(k-1)}
\lt 1+\dfrac23\dfrac{2}{k-3}
= 1+\dfrac{4}{3(k-3)}
$.
Therefore
$\dfrac{k(k-1)}{2\log(2)}
\lt n
\lt \dfrac{k(k-1)}{2\log(2)}+\dfrac{2k(k-1)}{3\log(2)(k-3)}
$.
In particular,
$n
=\dfrac{k^2}{2\log(2)}+O(k)
$
or
$k
=\sqrt{2n\log(2)}+O(1)
$.
