3
$\begingroup$

I am having some difficulty with multivariable asymptotics. Let me provide a concrete example of the kind of thing I mean.

Stirling's approximation for $n!$ is

$ n! \sim \sqrt{2 \pi n}\left( \frac{n}{e} \right)^n. $

For ease of notation, denote the right-hand side of the above by $S(n)$. The precise meaning of $\sim$ is that

$ \lim_{n \rightarrow \infty} \frac{n!}{S(n)} = 1. $

Suppose now we have a new variable $k$ and want to ask about the asymptotics of $(n!)^k$ where $k$ is allowed to grow with $n$. A proposed asymptotic expression may not (likely does not) exist if $n$ and $k$ are allowed to grow at arbitrary rates. Instead, I would like to view $k$ as a function $k(n)$ and determine the largest possible order of growth for $k(n)$ for which a proposed asymptotic formula will hold. A way to begin might be to ask what is the largest possible order of growth for which

$ \lim_{n \rightarrow \infty} \frac{(n!)^{k(n)}}{(S(n))^{k(n)}} = 1. $

How might one approach such a problem?

1 Answers 1

1

To be able to find $k(n)$ we must know about the secondary terms in Stirlings formula. Specifically this Wikipedia page tells us that more precisely $n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}\left(1+\frac{1}{12n}+O\left(\frac{1}{n^{2}}\right)\right).$

Consequently, if we take $k(n)=n$, we see that the asymptotic will not hold. This is because the $\left(1+\frac{1}{12n}\right)^n$ cannot be ignored as $\left(1+\frac{1}{12n}\right)^{n}\rightarrow e^{\frac{1}{12}}\neq1.$

So, we now know that if $k(n)$ grows like a constant multiple of $n$, or faster then $n$, the asymptotic will not work out. What about slower then $n$? What if $k(n)=o(n)$? Well, we can prove that $\left(1+\frac{1}{12n}\right)^{k(n)}\rightarrow 1$ as $n\rightarrow \infty$ whenever $k(n)=o(n)$, (exercise for you) and hence the asymptotic $(n!)^{k(n)}\sim \left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}\right)^{k(n)}$ does hold.

Hope that helps,

  • 0
    I used a slightly different approach, but I also arrived at $o(n)$ being the best possible. Thanks for your help.2011-05-29