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?

$\endgroup$
1
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ I used a slightly different approach, but I also arrived at $o(n)$ being the best possible. Thanks for your help. $\endgroup$ – Austin Mohr May 29 '11 at 23:13

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.