The Birthday Problem

 

Assumed Approximations                      

The proof rests on two well-known approximations:

 Note that 

In general, if  a<< n:

[A] 

 Note that 

In general, if  i<< j:

[B] 

  1. Return to the Proof