I want to show the following limit: $$ \lim_{n \to \infty} n \left[ \left( 1 - \frac{1}{n} \right)^{2n} - \left( 1 - \frac{2}{n} \right)^{n} \right] = \frac{1}{e^{2}}. $$ I got the answer using WolframAlpha, and it seems to be correct numerically, but I am having trouble proving the result. My first instinct was to write the limit as $$ \lim_{n \to \infty} \frac { \left( 1 - \frac{1}{n} \right)^{2n} - \left( 1 - \frac{2}{n} \right)^{n} } {1/n}. $$ Then, I tried applying l'Hopital's rule, and I got $$ \lim_{n \to \infty} \frac { \left( 1 - \frac{1}{n} \right)^{2n} \left( 2 \log\left( 1 - \frac{1}{n} \right) + \frac{2}{n-1} \right) - \left( 1 - \frac{2}{n} \right)^{n} \left( \log\left( 1 - \frac{2}{n} \right) + \frac{2}{n-2} \right) } {-1/n^{2}}. $$ This does not seem to have gotten me anywhere. My second attempt was to use the binomial theorem: $$ \begin{align*} n \left[ \left( 1 - \frac{1}{n} \right)^{2n} - \left( 1 - \frac{2}{n} \right)^{n} \right] & = n \left[ \sum_{k=0}^{2n} \binom{2n}{k} \frac{(-1)^{k}}{n^{k}} - \sum_{k=0}^{n} \binom{n}{k} \frac{(-1)^{k} 2^{k}}{n^{k}} \right] \\ & = \sum_{k=2}^{n} \left[ \binom{2n}{k} - \binom{n}{k} 2^{k} \right] \frac{(-1)^{k}}{n^{k-1}} + \sum_{k=n+1}^{2n} \binom{2n}{k} \frac{(-1)^{k}}{n^{k-1}}. \end{align*} $$ At this point I got stuck again.
-
1Do you know the Taylor series of $\log (1+x)$? – Daniel Fischer May 14 '15 at 21:09
-
Is this question by any chance inspired by my comment on this post ? :-$)$ – Lucian May 14 '15 at 22:53
-
In general, $$\lim_{n\to\infty}n~\bigg[\bigg(1+\frac1n\bigg)^{an} - \bigg(1+\frac an\bigg)^n\bigg] ~=~ \frac{a(a-1)}2~e^a,$$ and $$\lim_{n\to\infty}n~\bigg[\bigg(1-\frac1n\bigg)^{an} - \bigg(1-\frac an\bigg)^n\bigg] ~=~ \frac{a(a-1)}2~e^{-a}.$$ – Lucian May 14 '15 at 22:59
-
@Lucian -- I was unaware of your question, but that is a very nice result! I encountered the limit in this question while trying to find an asymptotic formula for the variance of the number of distinct items present when bootstrapping a data set of size $n$. The answer ended up being $n (e^{-1} - 2 e^{-2})$. – Stirling May 15 '15 at 00:37
-
As an aside, $~\displaystyle\prod_{n=1}^\infty\frac{\bigg(1+\dfrac1n\bigg)^a}{1+\dfrac an}=a!$ – Lucian May 15 '15 at 05:29
4 Answers
I would do the transform $$\left(1-\frac{1}{n}\right)^{2n}=e^{2n\log\left(1-\frac{1}{n}\right)}$$ then use the second order Taylor expansion $$\log(1+x)\approx x-\frac{x^2}{2}$$ and similarly for the other term, obtaining $$ n\left(e^{-2-\frac{1}{n}}-e^{-2-\frac{2}{n}}\right)=e^{-2-\frac{2}{n}}\cdot\frac{e^{\frac{1}{n}}-1}{\frac{1}{n}} $$
- 10,955
We can proceed in the following manner \begin{align} L &= \lim_{n \to \infty}n\left\{\left(1 - \frac{1}{n}\right)^{2n} - \left(1 - \frac{2}{n}\right)^{n}\right\}\notag\\ &= \lim_{n \to \infty}n\left(1 - \frac{2}{n}\right)^{n}\left\{\dfrac{\left(1 - \dfrac{1}{n}\right)^{2n}}{\left(1 - \dfrac{2}{n}\right)^{n}} - 1\right\}\notag\\ &= \frac{1}{e^{2}}\lim_{n \to \infty}n\left\{\dfrac{\left(1 - \dfrac{2}{n} + \dfrac{1}{n^{2}}\right)^{n}}{\left(1 - \dfrac{2}{n}\right)^{n}} - 1\right\}\notag\\ &= \frac{1}{e^{2}}\lim_{n \to \infty}n\left\{\left(1 + \frac{1}{n^{2} - 2n}\right)^{n} - 1\right\}\notag\\ &= \frac{1}{e^{2}}\lim_{n \to \infty}f(n)\tag{1} \end{align}
Now note that \begin{align} n\left(1 + \frac{n}{n^{2} - 2n} - 1\right) < f(n) &= n\left[\left\{\left(1 + \frac{1}{n^{2} - 2n}\right)^{n^{2} - 2n}\right\}^{n/(n^{2} - 2n)} - 1\right]\notag\\ &< n\left\{\exp\left(\frac{n}{n^{2} - 2n}\right) - 1\right\}\notag\\ &= n\cdot\frac{n}{n^{2} - 2n}\cdot\frac{n^{2} - 2n}{n}\left\{\exp\left(\frac{n}{n^{2} - 2n}\right) - 1\right\}\notag\\ \end{align} and we get $$\frac{n^{2}}{n^{2} - 2n} < f(n) < \frac{n^{2}}{n^{2} - 2n}\cdot\frac{n^{2} - 2n}{n}\left\{\exp\left(\frac{n}{n^{2} - 2n}\right) - 1\right\}$$ Taking limits as $n \to \infty$ and using squeeze theorem we see that $f(n) \to 1$ as $n \to \infty$. From equation $(1)$ we can see that $L = 1/e^{2}$.
In order to derive the inequalities we have used $(1 + x)^{n} > 1 + nx$ for $x > 0$ and $n$ a positive integer and $(1 + (1/n))^{n} < e$ for all positive integers $n$. Both these inequalities are pretty standard and can be easily proved. Also note that if we put $t = n/(n^{2} - 2n)$ then $t \to 0$ as $n \to \infty$ and hence $(e^{t} - 1)/t \to 1$ as $n \to \infty$.
- 87,309
$$ (1-\frac1{n})^{2n} =(1-\frac2{n}+\frac1{n^2})^n $$ use the binomial expansion: $$ (1-\frac2{n}+\frac1{n^2})^n =\sum_{k=0}^n(1-\frac2{n})^{n-k}\binom{n}{k}\frac1{n^{2k}} $$ so $$ n \left[ \left( 1 - \frac{1}{n} \right)^{2n} - \left( 1 - \frac{2}{n} \right)^{n} \right] = \sum_{k=1}^n(1-\frac2{n})^{n-k}\binom{n}{k}\frac1{n^{2k-1}} \\ =(1-\frac2{n})^{n-1}+\sum_{k=2}^n(1-\frac2{n})^{n-k}\binom{n}{k}\frac1{n^{2k-1}} $$
- 18,040
In the same spirit as Lucian, you can consider the general expansion for large values of $n$ $$ \left( 1 - \frac{a}{n} \right)^{b\,n}= \left(1-\frac{a^2 b}{2 n}+\frac{a^3 b (3 a b-8)}{24 n^2}-\frac{a^4 b \left(a^2 b^2-8 a b+12\right)}{48 n^3}+\cdots\right)e^{-a b} $$ Applied to your case $$\left( 1 - \frac{1}{n} \right)^{2n}=\left(1-\frac 1n-\frac1 {6n^2}+\cdots\right)e^{-2}$$ $$\left( 1 - \frac{2}{n} \right)^{n}=\left(1-\frac 2n-\frac2 {3n^2}+\cdots\right)e^{-2}$$ which finally make $$n \left[ \left( 1 - \frac{1}{n} \right)^{2n} - \left( 1 - \frac{2}{n} \right)^{n} \right]=\left( 1 +\frac{1}{2n}+\cdots \right)e^{-2}$$
In a more general manner,$$\left[ \left( 1 - \frac{a}{n} \right)^{bn} - \left( 1 - \frac{b}{n} \right)^{an} \right]=(a-b)\left(-\frac{a b }{2 n}+\frac{a b (a+b) (3 a b-8)}{24 n^2}\right)e^{-ab}$$
- 260,315