3
$\begingroup$

I'm trying to understand the reasoning in the following step of a limit analysis:

$$\lim_{n \to \infty} n\left(\left[1- \frac{1+c}{\frac{n}{\ln(n)}} \right]^{\frac{n}{\ln (n)}}\right)^{(n-1)\ln n/n} = \lim_{n \to \infty} ne^{-[(1+c)\ln(n)]}$$

I understand the "inner" part; $\lim_{n \to \infty} [1-\frac{1+c}{\frac{n}{\ln (n)}}]^{\frac{n}{\ln n}} = e^{-(1+c)}.$ And I sort of see that outer exponent $((n-1)\ln n) /n = (\ln n) - (\ln n / n)$ and the second part goes to 0, but it's not clear to me what rules actually justify "bringing the limit to the exponent". What are the actual steps involved in deducing this limit?

More generally, these types of asymptotic analysis show up in comp sci all the time and I feel there is a bag of tricks that I am missing.

$\endgroup$

2 Answers 2

1
$\begingroup$

You can't in general replace a sub-expression by its limit while evaluating the limit of a complicated expression. There are ways to do so in very specific circumstances when the sub-expression is a term or a factor in the whole expression, but otherwise this is not allowed.

A better strategy is to take logarithm and thus if $L$ is the desired limit then we have by continuity of logarithm $$\log L=\lim_{n\to\infty} \log n+(n-1) \log\left(1-\frac{(1+c)\log n} {n} \right) $$ and the expression under limit above can be written as $$\log n+n\log\left (1-\frac{(1+c)\log n} {n} \right) - \log\left(1-\frac{(1+c)\log n} {n} \right) $$ Clearly the last term tends to $0$ and hence we get $$\log L=\lim_{n\to\infty} \log n+n\log\left(1-\frac{(1+c)\log n} {n} \right) \tag{1}$$ If $t=(\log n)/n$ then we can write $$\log L=\lim_{n\to \infty} \log n\cdot\frac{t+\log(1-(1+c)t)}{t}$$ The second factor above tends to $-c$ and the fraction can thus be replaced by its limit $-c$ as long as $c\neq 0$.

Thus if $c\neq 0$ we get $$\log L=-\lim_{n\to\infty} c\log n$$ which means that $L=0$ if $c>0$ and $L=\infty$ if $c<0$.

If $c=0$ then we have more work to do. In that case $$\log L=\lim_{n\to\infty} \log n\cdot t\cdot\frac{t+\log(1-t)}{t^2}$$ and last factor tends to $-1/2$ and then we have $$\log L=-\frac{1}{2}\lim_{n\to\infty } \frac{(\log n) ^2}{n}=0$$ so that $L=1$ in this case.


Most cases of asymptotic analysis during evaluation of limit are nothing more than omission of valid steps (on the assumption that they are obvious to the reader) and may appear as tricks. But in reality they are nothing more than application of limit laws.

The specific treatment in your question is nothing more than applying Taylor series in equation $(1)$ and discarding all terms except the first because all the other terms tend to $0$. Thus we get from $(1)$ $$\log L=\lim_{n\to\infty } \log n-n\cdot(1+c)\frac{\log n} {n} $$ and thus $$L=\lim_{n\to\infty} ne^{-(1+c)\log n} =\lim_{n\to\infty} n^{-c} $$

$\endgroup$
0
$\begingroup$

For this limit, you can bring up the $\ln(n)$ from the denominator, and then make the exponent match by using $(a^b)^c = a^{bc}$:

$$ \lim_{n \to \infty} n\left(\left[1- \frac{(1+c)\ln(n)}{n} \right]^{\frac{n}{\ln (n)}}\right)^{\frac{(n-1)\ln n}{n}} = \lim_{n \to \infty} ne^{-[(1+c)\ln(n)]} \\ \lim_{n \to \infty} n\left(\left[1- \frac{(1+c)\ln(n)}{n} \right]^{n}\right)^{\frac{1}{\ln(n)} \cdot \frac{(n-1)\ln n}{n}} = \lim_{n \to \infty} ne^{-[(1+c)\ln(n)]} \\ \lim_{n \to \infty} n\left(\left[1- \frac{(1+c)\ln(n)}{n} \right]^{n}\right)^{\frac{n-1}{n}} = \lim_{n \to \infty} ne^{-[(1+c)\ln(n)]} $$

This particular problem can be simiplied further into a form that uses the common limit property $\lim_{x \to a}\left[\frac{f(x)}{g(x)}\right] = \frac{\lim_{x \to a}f(x)}{\lim_{x \to a}g(x)}$, so that we don't have to worry about whether a corresponding rule holds for exponents.

$$ \lim_{n \to \infty} n\left(\left[1- \frac{(1+c)\ln(n)}{n} \right]^{n-1}\right) = \lim_{n \to \infty} ne^{-[(1+c)\ln(n)]} \\ \frac{\lim_{n \to \infty} n\left(\left[1- \frac{(1+c)\ln(n)}{n} \right]^{n}\right)}{\lim_{n \to \infty} \left[1- \frac{(1+c)\ln(n)}{n} \right]} = \lim_{n \to \infty} ne^{-[(1+c)\ln(n)]} \\ \frac{\lim_{n \to \infty} ne^{-[(1+c)\ln(n)]}}{1-0} $$


Breaking down that last step for the numerator requires the chain rule for limits, which states that if $\lim_{u \to b} f(u) \to L$ and $\lim_{x \to a} g(x) = b$, and $f(x)$ is continuous at $x=b$, then $\lim_{x \to a} f(g(x)) \to L$. Colloquially, as the input to a function approaches some input limit, its output approaches some output limit, and we can link up the output limit of one function to be the input limit of another function.

$$ \lim_{n \to \infty} n\left(\left[1- \frac{(1+c)\ln(n)}{n} \right]^{n}\right) \\ \lim_{n \to \infty} n \cdot \lim_{n \to \infty} \left(\left[1- \frac{(1+c)\ln(n)}{n} \right]^{n}\right) \\ $$

Extracting out the inner function, define:

$$ g(n) = (1+c)\ln n \\ \lim_{n \to \infty} g(n) \to G $$

And now we can write our expression as:

$$ \lim_{n \to \infty} n \cdot \lim_{x \to G}\left[\lim_{n \to \infty} \left(\left[1- \frac{G}{n} \right]^{n}\right)\right] \\ $$

But whatever G may end up being, this portion of behavior as $n \to \infty$ is well defined as $e^x$, whatever the argument $x$ approaches. G need not vary with n for this next step:

$$ \lim_{n \to \infty} n \cdot \lim_{x \to G} e^G $$

Running the chain rule back the other direction, substituting back in for G:

$$ \lim_{n \to \infty} n \cdot \lim_{n \to \infty} e^{(1+c)\ln n} $$

And running the product rule in reverse, we have the desired

$$ \lim_{n \to \infty} ne^{(1+c)\ln n} $$

$\endgroup$
7
  • $\begingroup$ But why can I evaluate the exponent $(n-1)/n$ a a limit independently of the rest of the limit? $\endgroup$
    – theQman
    Commented Jan 15, 2021 at 22:41
  • $\begingroup$ Oh, I see what you mean. Yeah, maybe the inside limit doesn't converge independently, and really there's some combined effect that gets evaluated. Hm... $\endgroup$
    – epte
    Commented Jan 15, 2021 at 22:43
  • $\begingroup$ I wonder if your underlying question is something more like, "can you distribute limits through an exponent? Does lim g^f imply (lim g)^(lim f)?" I edited the answer to avoid that question, showing how this problem could be solved without it. Or is the question more "Can we partially evaluate limits like in the last step numerator? $\endgroup$
    – epte
    Commented Jan 15, 2021 at 23:03
  • $\begingroup$ Yes, that's the sort of general picture I'm trying to gain a better understanding of... In terms of your answer, I'm not sure how you get $\lim n ([1-\frac{(1+c) \ln (n)}{n}]^n) = \lim n e^{-[(1+c) \ln (n)]}$. I think you're implicitly using the product rule and then evaluating $\lim ([1-\frac{(1+c) \ln (n)}{n}]^n) = e^{-[(1+c) \ln (n)]}$, but does this make sense when we still get a function of $n$ after taking $n \to \infty$? $\endgroup$
    – theQman
    Commented Jan 16, 2021 at 16:37
  • $\begingroup$ I have edited my answer to break down the last step using the chain rule for limits. Are there any remaining areas of confusion? $\endgroup$
    – epte
    Commented Jan 16, 2021 at 22:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .