The proof rests on two well-known approximations:

 Note that 

In general, if  a<< n:

[A] 

 Note that 

In general, if  i<< j:

[B] 

Home | The Birthday Problem | A Generalization | The Proof