Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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,

share|improve this answer
    
I used a slightly different approach, but I also arrived at $o(n)$ being the best possible. Thanks for your help. –  Austin Mohr May 29 '11 at 23:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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