[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Suppose that on planet Zorg a year has

[math]n[/math] days, and that the lifeforms there are equally likely to have hatched on any day of the year. We would like to estimate [math]d[/math], which is the minimum number of lifeforms needed so that the probability of at least two sharing a birthday exceeds 1/2.

• In Example, it was shown that in a set of [math]d[/math] lifeforms, the probability that no two life forms share a birthday is
  [[math]] {{(n)_d}\over{n^d}}\ , [[/math]]
  where [math](n)_d = (n)(n-1)\cdots (n-d+1)[/math]. Thus, we would like to set this equal to 1/2 and solve for [math]d[/math].
• Using Stirling's Formula, show that
  [[math]] {{(n)_d}\over{n^d}} \sim \biggl(1 + {d\over{n-d}}\biggr)^{n-d + 1/2} e^{-d}\ . [[/math]]
• Now take the logarithm of the right-hand expression, and use the fact that for small values of [math]x[/math], we have
  [[math]] \log(1+x) \sim x - {{x^2}\over 2}\ . [[/math]]
  (We are implicitly using the fact that [math]d[/math] is of smaller order of magnitude than [math]n[/math]. We will also use this fact in part (d).)
• Set the expression found in part (c) equal to [math]-\log(2)[/math], and solve for [math]d[/math] as a function of [math]n[/math], thereby showing that
  [[math]] d \sim \sqrt{2(\log 2)\,n}\ . [[/math]]
  Hint: If all three summands in the expression found in part (b) are used, one obtains a cubic equation in [math]d[/math]. If the smallest of the three terms is thrown away, one obtains a quadratic equation in [math]d[/math].
• Use a computer to calculate the exact values of [math]d[/math] for various values of [math]n[/math]. Compare these values with the approximate values obtained by using the answer to part d).