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.
 A: 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)
$.
A: In addition to @martycohen's accepted answer, I share (for future reference) my failing attempt to prove something valid for all $0 < \alpha < 1$, instead of $1/2$.
For each $0 < \alpha < 1$ fixed, we want to find $k=k(n)$ such that:
$$P(k,n):=\prod_{j=0}^{k−1}\Big(1−\frac jn\Big)=\alpha.$$
This is equivalent to
$$\sum_{j=0}^{k−1}- \log\Big(1−\frac jn\Big)=\log(1/\alpha).$$
Since $x \leq -\log (1-x)$ on $[0,1]$ (easy to prove) , we have:
$$\frac 1 n \sum_{j=0}^{k-1} j \leq \log(1/\alpha)$$
i.e.
$$\frac {k(k-1)}{2n}  \leq \log(1/\alpha)$$
A simple computation (root of polynomial in $k$ of degree $2$) shows that a necessary condition is that $k$ has to be chosen:
$$k \leq 1/2 + 1/2 \sqrt{1 + 8 \log(1/\alpha) n}.$$
If $\alpha$ is fixed, and $n$ is large enough, we can assume $k \leq n /2$, then the terms $j/n$ in the following sum will be: $j/n < k/n \leq 1/2$.
[Not very good here because we would like an estimate uniform for all $0 < \alpha < 1$, and $n \geq 1$, i.e. without requiring "$n$ large enough"]
Now we can use $-\log(1-x) \leq x + x^2$ which is true on $[0, 1/2]$ (*) (easy to prove).
Then:
$$\log(1/\alpha) = \sum_{j=0}^{k−1}- \log\Big(1−\frac jn\Big) \leq \frac 1 n \sum_{j=0}^{k-1} j + \frac 1 {n^2} \sum_{j=0}^{k-1} j^2$$
i.e.
$$\log(1/\alpha) \leq \frac {k(k-1)}{2 n} + \frac {k(k-1)(2k-1)}{6 n^2}$$
Here I cannot get a satisfying upper bound because $k$'s upper bound (see necessary condition before) involves $\sqrt{\log(1/\alpha)}$ which can be arbitrarily large if $\alpha$ is very close to $0$.
To be continued!

Note: (*) I used this on $[0, 1/2]$ because it's hopeless to get an upper bound on $[0,1]$ as a polynomial because the function $f(x):=-\log(1-x)$ tends to $+\infty$ when $x$ approaches $1$:

That's why @martycohen's upper bound $−\log(1−x)< x + x^2 / (2(1−x))$ is more appropriate because valid on $[0,1[$.
