Showing posts with label Gosper. Show all posts
Showing posts with label Gosper. Show all posts

06 November 2007

Gosper's modification of Stirling's approximation

From Math Forum: an improvement of Stirling's approximation, credited to Gosper:
n! \approx \sqrt{\left(2n + {1 \over 3} \right) \pi} \left( {n \over e} \right)^n

The usual approximation is
n! \approx \sqrt{2\pi n} \left( {n \over  e} \right)^n

which is just the beginning of an asymptotic series
n! \sim \sqrt{2\pi n} \left( {n \over  e} \right)^n \left( 1 + {1 \over 12n} + O(n^{-2}) \right)

and we can rewrite the square root to get
\sqrt{2 \pi n} \left( 1  + {1 \over 12n} \right) = \sqrt{2 \pi n} \sqrt{1 + {1 \over 6n} + O(n^{-2})}

and combining the two square roots gives us
n! = \sqrt{\left( 2n+{1 \over 3} \right)\pi} \left( { n \over e} \right)^n (1 + O(n^{-2}))

which is what we wanted. This is basically a combination of the first two terms of the usual Stirling approximation into one term. For example, when n = 8 this gives 40316, compared to 39902 for the first term of Stirling's series and 40318 for the first two. (8! = 40320.) In general the error of Gosper's approximation is about twice that in the first two terms of Stirling's, so this isn't incredibly useful but it's an interesting curiosity.