Limit of $\left(1-\frac{c f(n)}{n}\right)^n$

Question

I know that $(1-1/n)^n \approx 1/e$, but what is the result for $\left(1-\frac{c f(n)}{n}\right)^n$, where $c$ is an arbitrary constant and $f(n)$ is an arbitarry function of $n$?

I am asking because I am having trouble understanding these derivations: $E(x)=\binom{n}{2} (1-p)(1-p^2)^{n-2}$

Let $p=c \sqrt{\ln n / n}$

$E(x) \approx n^2/2 (1-c \sqrt{\ln n / n})(1-c^2 \ln n / n)^n$

$\approx n^2/2 e^{-c^2\ln n} \approx 1/2 n^{2-c^2}$

For $c>\sqrt 2$, then $E(x) \to 0$

Source: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf, page 11

Answer 1

You cannot say much about an arbitrary function of $n$: the result will depend on the function.

For instance, for $f(n)=1/n$ $$ \left(1+\frac{1}{n^2}\right)^n \xrightarrow[n\to\infty]{} 1 $$ while for $f(n) = n$, of course $$ \left(1+1\right)^n \xrightarrow[n\to\infty]{} \infty\,. $$ and for say $f(n) = -\sqrt{n}$ $$ \left(1-\frac{1}{\sqrt{n}}\right)^n \xrightarrow[n\to\infty]{} 0\,. $$

---

In your specific case, however, for $f(n) = -c^2 \ln n$, $$ \left(1-\frac{c^2\ln n}{n}\right)^n = e^{n\ln\left(1-\frac{c^2\ln n}{n}\right)} = e^{-c^2\ln n + o(1)} = \frac{1+o(1)}{n^{c^2}} \xrightarrow[n\to\infty]{} 0\,, $$ using that $\ln(1+u)=u+O(u^2)$ when $u\to 0$.

Answer 2

You have to set the following change of variable x= -n/c. Then your equation become : ((1+1/x)^x)^-c. Because c is a constant you can pass the limit into the exponential and when x goes to infinity, you find e^-c

Answer 3

As already pointed out it depends upon the particular function $f(n)$ chosen, indeed by simple examples we see that

• $f(n)=\frac n c\implies \left(1-\frac{c f(n)}{n}\right)^n=(1-1)^n=0$

• $f(n)=-\frac 1 c\implies \left(1-\frac{c f(n)}{n}\right)^n=\left(1+\frac{1}{n}\right)^n\to e$

Answer 4

The author seems to be indulging in the kind of loosey-goosey reasoning mathematicians love to hate: Because $(1-{x\over n})^n\approx e^{-x}$ when $n$ is large and $x$ is small, and because $\ln n$ is small compared to $n$ when $n$ is large, they are saying, in effect, that

$$\left(1-{\ln n\over n}\right)^n\approx e^{-\ln n}={1\over n}$$

It's worth checking how good the comparison is for a few values of $n$:

$$\begin{align} \left(1-{\ln100\over100}\right)^{100}&=0.00896362657\ldots\approx0.01\\ \left(1-{\ln1000\over1000}\right)^{1000}&=0.00097631598\ldots\approx0.001\\ \left(1-{\ln10000\over10000}\right)^{10000}&=0.00009957648\ldots\approx0.0001 \end{align}$$

You can see that the approximations do seem to be getting better, but what's missing (certainly here) is any technical description of what "getting better" means. Perhaps a closer reading of the source might find an argument that more formally justifies the approximations being made.