I have been trying to derive the formula for the upper bound probability of the birthday paradox for any number of occurrences $n$.
Assuming we want to find the number of occurrences $k$ such that there is >50% probability they share a property, I am given it to be: $exp(-k(k-1)/2n)$
Now given the fact that P[share a property] = $\frac{1}{2}$ = $exp(-k(k-1)/2n)$, I would like to find the formula for $k$, so I can just plug in any $n$, to see the number of occurrences required with different values of $n$. This is only an approximation, so I need the formula to be in the form k ≈ ...
I have tried solving for $k$, but got stuck after getting rid of the exponential, which I'm not sure I even did correctly, as it gave me: $2n\ ln(2) < k^2-k$
I managed to find an answer to this online which said that $k ≈ 1.18\sqrt{n}$, but I have no idea how to get to that answer.
Since we are finding an approximation for $k$, we should have equality in $2n\ln2<k^2-k$, not just an inequality. The approximation comes after the quadratic formula. $$k^2-k-2n\ln2=0$$ $$k=\frac{1+\sqrt{1+8n\ln2}}2\approx\sqrt{2n\ln2}=\sqrt{2\ln2}\sqrt n$$ and $\sqrt{2\ln2}=1.17741\dots$