Stirling's approximation

In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of . It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre. One way of stating the approximation involves the logarithm of the factorial: where the big O notation means that, for all sufficiently large values of , the difference between and will be at most proportional to the logarithm. In computer science applications such as the worst-case lower bound for comparison sorting, it is convenient to use instead the binary logarithm, giving the equivalent form The error term in either base can be expressed more precisely as , corresponding to an approximate formula for the factorial itself, Here the sign means that the two quantities are asymptotic, that is, that their ratio tends to 1 as tends to infinity. The following version of the bound holds for all , rather than only asymptotically: Roughly speaking, the simplest version of Stirling's formula can be quickly obtained by approximating the sum with an integral: The full formula, together with precise estimates of its error, can be derived as follows. Instead of approximating , one considers its natural logarithm, as this is a slowly varying function: The right-hand side of this equation minus is the approximation by the trapezoid rule of the integral and the error in this approximation is given by the Euler–Maclaurin formula: where is a Bernoulli number, and Rm,n is the remainder term in the Euler–Maclaurin formula. Take limits to find that Denote this limit as . Because the remainder Rm,n in the Euler–Maclaurin formula satisfies where big-O notation is used, combining the equations above yields the approximation formula in its logarithmic form: Taking the exponential of both sides and choosing any positive integer , one obtains a formula involving an unknown quantity .