Editing Birthday problem (section)

==An upper bound on the probability and a lower bound on the number of people==
The argument below is adapted from an argument of [[Paul Halmos]].{{refn|group=nb|In his autobiography, Halmos criticized the form in which the birthday paradox is often presented, in terms of numerical computation.  He believed that it should be used as an example in the use of more abstract mathematical concepts. He wrote:
<blockquote>The reasoning is based on important tools that all students of mathematics should have ready access to.  The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What [[calculator]]s do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories.</blockquote>}}

As stated above, the probability that no two birthdays coincide is

:<math>1-p(n) = \bar p(n) = \prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right) .</math>

As in earlier paragraphs, interest lies in the smallest {{mvar|n}} such that {{math|''p''(''n'') > {{sfrac|1|2}}}}; or equivalently, the smallest {{mvar|n}} such that {{math|''{{overline|p}}''(''n'') < {{sfrac|1|2}}}}.

Using the inequality {{math|1 − ''x'' < ''e''<sup>−''x''</sup>}} in the above expression we replace {{math|1 − {{sfrac|''k''|365}}}} with {{math|''e''<sup>{{frac|−''k''|365}}</sup>}}. This yields

:<math>\bar p(n) = \prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right) < \prod_{k=1}^{n-1}\left(e^{-\frac{k}{365}}\right) = e^{-\frac{n(n-1)}{730}} .</math>

Therefore, the expression above is not only an approximation, but also an [[upper bound]] of {{math|''{{overline|p}}''(''n'')}}. The inequality

:<math> e^{-\frac{n(n-1)}{730}} < \frac{1}{2}</math>

implies {{math|''{{overline|p}}''(''n'') < {{sfrac|1|2}}}}. Solving for {{mvar|n}} gives

:<math>n^2-n > 730 \ln 2 .</math>

Now, {{math|730 ln 2}} is approximately 505.997, which is barely below 506, the value of {{math|''n''<sup>2</sup> − ''n''}} attained when {{math|''n'' {{=}} 23}}. Therefore, 23 people suffice. Incidentally, solving {{math|''n''<sup>2</sup> − ''n'' {{=}} 730 ln 2}} for ''n'' gives the approximate formula of Frank H. Mathis cited above.

This derivation only shows that ''at most'' 23 people are needed to ensure the chances of a birthday match are at least even; it leaves open the possibility that {{mvar|n}} is 22 or less could also work.