I have two related questions. Both are related to the asymptotics of Stirling's approximation, which is why I have included them in the same question. I will separate the questions if it is deemed necessary.

Consider Stirling's approximation. $$n! = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \left( 1 + O \left(\frac{1}{n} \right)\right)$$ $$\lim_{n \rightarrow \infty} \frac{n!}{\sqrt{2 \pi n} \left( \frac{n}{e} \right)^n} = 1$$ The exact terms of the expression are more precisely described by Stirling's series. Unfortunately the series is not convergent so at some point, for each particular $n$ there is a term $a_{f(n)}$ of the expansion at which point summing terms increases the magnitude of relative error.

$f : \mathbb{N}^+ \rightarrow \mathbb{N}$ and for $n$ in the domain, $f(n)$ is defined as rank at which the magnitude of the terms in the asymptotic expansion of the ratio $\frac{n!}{\sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \left(1+ \frac{1}{12n} + \cdots\right)}$ begins to increase.

My first question is what is known about $f(n)$? I believe it is known that $f(n)$ is monotonically increasing. Do we know the asymptotic growth of $f(n)$? If so, is there a known simple closed form expression for $f(n)$?

My second question has to do with error rates of Stirling's approximation and it depends on the first question having been resolved. Of course it is known that in the limit the relative error of approximating the factorial of $n$ approaches $0$. However, if one were to be interested in precisely how quickly the series well approximates the function, simple convergence in the limit is not enough. I would like to know the rate of convergence for the sequence $g(n) = \sum\limits_{i=0}^{f(n)} {a_i}$ in approximating $n!$. (Here $a_i$ are terms of the Stirling series).

  • $\begingroup$ Since you are using $O \left(\frac{1}{n} \right)$, you can write equality in $$n! = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \left( 1 + O \left(\frac{1}{n} \right)\right)$$ By $f$, do you mean $1 + O \left(\frac{1}{n} \right)$? $\endgroup$ – robjohn Nov 4 '11 at 8:54
  • $\begingroup$ I am not sure whether $f(n) = 1 + O(n^{-1})$. What I mean is, at some point summing terms of the Stirling series stops to increase the accuracy of the approximation (for any given $n$). I want to analyze, as $n$ increases, where one needs to stop summing terms of the series to get the best approximation. $\endgroup$ – Jason Knight Nov 4 '11 at 9:07
  • $\begingroup$ Okay, so by $f(n)$, you mean $\frac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}$ which is what I meant by $1+O\left(\frac{1}{n}\right)$. $\endgroup$ – robjohn Nov 4 '11 at 9:17
  • $\begingroup$ Formula 6 in the MathWorld entry you linked to gives a few more terms of Stirling's series. Temme mentions a few useful estimates for the remainder after truncating the Stirling series $\endgroup$ – J. M. isn't a mathematician Nov 4 '11 at 9:21
  • $\begingroup$ @robjohn: Could you expand more on your reasoning that that $f(n) = 1 + O(n^{-1})$ so that I know what you mean, especially since I would expect the range of $f$ to be $\mathbb{N}$. $\endgroup$ – Jason Knight Nov 4 '11 at 9:34

Temme's book, suggested by J.M., offers an explicit analysis of the remainder terms. However, he does not do it for the Stirling's series of $n!$, but for a similar large $n$ asymptotic expansion of $\ln n!$: $$ \ln n! \sim n(\ln n - 1) + \frac{1}{2}(\ln n + \ln 2\pi) + \frac{1}{2}\sum_{k=1}^{\infty} R_k,\quad\mbox{where}\quad R_k=\frac{B_{2k}}{k(2k-1)n^{2k-1}}\qquad (1) $$ and $B_{2k}$ denote Bernoulli numbers, see DLMF. On p.65 Temme shows that error of the truncated expansion is bounded by the magnitude of the first neglected term. Hence, the optimal truncation is at the smallest term in the sum. Keeping in mind that $B_{2k}\sim 4\sqrt{\pi k}(k/\pi e)^{2k}$, you can write $$ R_k\sim \frac{4\sqrt{k}}{\sqrt{\pi}e(2k-1)} \left(\frac{k}{\pi e n}\right)^{2k-1}. $$ The first factor is irrelevant to the leading order. It is then an easy exercise to establish that when $C$ is large, the minimum of the function $(x/C)^{2x-1}$ is achieved when $x\approx C/e$. Therefore, the optimal trancation is achieved at $k\approx\pi n$, so your $f(n)\approx\pi n$, just as obtained by robjohn.

This result may be confirmed by plotting the relative errors obtained when using expansions (1) truncated at $N$th term. The red curve is computed for $n=10$, whereas the blue curve is computed for $n=20$.

enter image description here

A similarly simple formula for $f(n)$ in the case of Stirling's series is not very likely to exist, because the late terms of Stirling's series do not decrease (or increase) in a monotonic fashion, see W. G. C. Boyd "Gamma Function Asymptotics by an Extension of the Method of Steepest Descents", Proc. R. Soc. Lond. A, 447(1931), 609-630 (1994). However, Boyd's paper does offer state-of-the-art analysis of the remainder error of the truncated Stirling's series, so it does offer an answer to your second question. Boyd also provides simple asymptotic expressions for the coefficients of Stirling's series, so you should be able to construct an asymptotic for $f(n)$ from the results given in his paper.

  • 1
    $\begingroup$ @J.M. This is very embarrassing! Many thanks for correcting these for me. $\endgroup$ – Aleksey Pichugin Nov 5 '11 at 10:37
  • 1
    $\begingroup$ That's 'cause I care. ;) $\endgroup$ – J. M. isn't a mathematician Nov 5 '11 at 10:54

The Euler-Maclaurin Sum Formula has the form $$ \sum_{k\le n}\;f(k)=\int^n f(x)\;\mathrm{d}x+\frac{1}{2}f(n)+\sum_{k\ge1}a_{2k}f^{(2k-1)}(n)\tag{1} $$ where $\limsup\limits_{k=\infty}\;|a_{2k}|^{1/k}=\dfrac{1}{4\pi^2}$. This is because $$ \frac{x}{1-e^{-x}}=\sum_{k=0}^\infty a_kx^k\tag{2} $$ and the series in $(2)$ has a radius of convergence of $2\pi$.

For $\log(n!)$, $f(n)=\log(n)$, so $|f^{(2k-1)}(n)|=\dfrac{(2k-2)!}{n^{2k-1}}$. Therefore, the terms in the Euler-Maclaurin series for $\log(n!)$ grow somewhat like $\dfrac{(2k-2)!}{(2\pi n)^{2k-1}}$. Since the series for each $e^{n^{-k}}$ converges (when exponentiating the asymptotic expansion for $\log(n!)$), I would expect that the terms in the asymptotic series for $\frac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}$ would also grow in the same manner. Therefore, it would be my guess that the terms in Stirling's formula would start to increase when $k\sim\pi n$.

  • $\begingroup$ Numerical examination of the coefficients of the Euler-Maclaurin Sum Formula, indicate that the ratios of the coefficients is about $\frac{1}{4\pi^2}$. $\endgroup$ – robjohn Nov 4 '11 at 15:33

Stirling's expansion can be written as $$n! \sim \sqrt {2\pi } n^{n+1/2} e^{ - n} \sum\limits_{k = 0}^\infty {\left( { - 1} \right)^k \frac{{\gamma _k }}{{n^k }}}.$$ It is known that $$ \gamma _{2k + 1} = \frac{{\left( { - 1} \right)^k }}{\pi }\frac{{\Gamma \left( {2k + 1} \right)}}{{\left( {2\pi } \right)^{2k + 1} }}\left( {1 + O\left( {\frac{1}{k}} \right)} \right) = \frac{{\left( { - 1} \right)^k }}{{\pi e^{ - 1} }}\left( {\frac{k}{{\pi e}}} \right)^{2k + 1} \sqrt {\frac{\pi }{k}} \left( {1 + O\left( {\frac{1}{k}} \right)} \right) $$ and $$ \gamma _{2k} = \frac{{\left( { - 1} \right)^{k + 1} }}{6}\frac{{\Gamma \left( {2k - 1} \right)}}{{\left( {2\pi } \right)^{2k} }}\left( {1 + O\left( {\frac{1}{k}} \right)} \right) = \frac{{\left( { - 1} \right)^{k + 1} }}{{12}}\left( {\frac{k}{{\pi e}}} \right)^{2k} \sqrt {\frac{\pi }{{k^3 }}} \left( {1 + O\left( {\frac{1}{k}} \right)} \right) $$ as $k\to +\infty$. So $f(n) \approx 2\pi n$ for large $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.