0
$\begingroup$

By using limits, show that log n! ∈ Θ(n logn).

Using Stirling's approximation for n! I get the limit: $$\lim_{n \to ∞} \frac{log({\sqrt{2πn}}*(\frac{n}{e})^n)}{nlogn} = constant > 0$$

When I break this down separately: $$\lim_{n \to ∞} \frac{\sqrt{2πn}}{n^n} * \lim_{n \to ∞} (\frac{n}{e})^n = constant > 0$$

To me, the left limit approaches 0 and the right limit approaches infinity. Can I not rewrite the limit like this? Or do I need to use L'Hopistal's rule? Because I don't understand how I would do that here.

$\endgroup$
2
  • $\begingroup$ You dropped the logarithms and created an undefined limit. This leads you nowhere. $\endgroup$
    – user16034
    Oct 28, 2022 at 15:18
  • $\begingroup$ @YvesDaoust O.o I was too quick and reading the question and I didn't realize that. In addition to your observation, the denominator of the first limit in the product is weird. $\endgroup$
    – Steven
    Oct 28, 2022 at 15:25

3 Answers 3

0
$\begingroup$

You have some algebra mistake but, in general, you are right that you cannot always rewrite a limit of products as the products of limits. Let $f(n)$ and $g(n)$ be two functions. Then $$\lim_{n \to \infty} f(n)g(n) = \lim_{n \to \infty} f(n) \cdot \lim_{n \to \infty} f(n)$$ only holds if $\lim_{n \to \infty} f(n)$ and $\lim_{n \to \infty} f(n)$ exist and are either both finite, or one is infinite and the other is not $0$.

To handle the original limit without using L'Hôpital's rule: $$ \begin{align*} \lim_{n \to \infty} \frac{\log n!}{n \log n} &= \lim_{n \to \infty} \frac{\log (\sqrt{2\pi n} \cdot (n/e)^n )}{n \log n}\\ & =\lim_{n \to \infty} \frac{\log \sqrt{2\pi n}}{n \log n} + \lim_{n \to \infty} \frac{\log (n/e)^n }{n \log n} \\ &=0 + \lim_{n \to \infty} \frac{n \log n }{n \log n} - \lim_{n \to \infty} \frac{n \log e}{n \log n} =1 - 0 = 1. \end{align*} $$

Therefore $\log n! \sim n \log n$.

$\endgroup$
1
$\begingroup$

$$\log\left(\sqrt{2\pi n}\left(\dfrac ne\right)^n\right)=\log\sqrt{2\pi}+\frac12\log n +n\log n-n.$$

Clearly, this expression is dominated by the term $n\log n$ and your limit is $1$.

$\endgroup$
6
  • $\begingroup$ This is a bit nitpicky, but since we don't know the base of the $\log$ you could replace the last term with $-n \log e$ to cover all bases (pun intended). $\endgroup$
    – Steven
    Oct 28, 2022 at 15:29
  • $\begingroup$ @Steven: in calculus, $\log$ is usually natural. $\endgroup$
    – user16034
    Oct 28, 2022 at 15:45
  • $\begingroup$ Everywhere, ln is always the natural logarithm. Should be used unless it doesn't matter. $\endgroup$
    – gnasher729
    Oct 28, 2022 at 16:51
  • $\begingroup$ @gnasher729: for some reason, on Mathematics 99% of the posts use $\log$. $\endgroup$
    – user16034
    Oct 28, 2022 at 16:59
  • $\begingroup$ Well, this is computer science, not mathematics. $\endgroup$
    – gnasher729
    Oct 29, 2022 at 22:09
0
$\begingroup$

You broke this down, but in a very unpractical way.

$\log {(n/e)^n} = n \log (n /e) = n (\log n - 1)$ is much more helpful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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