What is $$\lim_{n\rightarrow\infty}\left(1-\left(1-\frac1n\right)^{f(n)}\right)^{2f(n)}$$ when $f(n)$ grows faster than $n$? Is the limit $1$?
How fast should $f(n)$ grow for this to happen?
Asked
Active
Viewed 111 times
2
-
Have you tried $f(n)=n\log n$? – Jack D'Aurizio Jul 12 '16 at 23:59
-
$f(n)=n^{1+\epsilon}$ should suffice but sometimes wolfram alpha confuses me by throwing out $0$ that is why this problem – Turbo Jul 13 '16 at 00:01
-
you will often be confused by using wolfram – zhw. Jul 13 '16 at 00:46
-
limits don't converge; they either exist or they don't – zhw. Jul 13 '16 at 00:53
-
@zhw. ok............................. do you have other such oddities from wolfram? – Turbo Jul 13 '16 at 01:23
-
@Turbo The question that bugs me... where does that strange expression come from in the first place? – Clement C. Jul 13 '16 at 02:58
-
@ClementC. what is strange about this? – Turbo Jul 13 '16 at 03:22
-
@Turbo Nothing per se... it just doesn't seem like the first expression I'd think about on my spare time, so I was curious about whether it originated from some particular context. – Clement C. Jul 13 '16 at 03:24
-
@ClementC. from a cs theory problem – Turbo Jul 13 '16 at 03:24
-
@Turbo ack. Thanks! – Clement C. Jul 13 '16 at 03:26
-
@ClementC. only in theory we get such strange items. what does tl;dr: mean? – Turbo Jul 13 '16 at 03:26
-
1"Too long; didn't read." It's commonly used to introduce a summary or condensed version of something much longer that follows. – Clement C. Jul 13 '16 at 03:29
-
@ClementC. I saw something in hamiltonian cycles somewhere it gives something like this (may be dirichlet's theorem?). – Turbo Jul 13 '16 at 03:31
2 Answers
3
tl;dr: the limit could be anything in $[0,1]$.
Let $f$ be a function of the form $$ f(n) = n g(n) $$ with $g(n)\xrightarrow[n\to\infty]{} \infty$. Then we can write $$ \left(1-\left(1-\frac1n\right)^{f(n)}\right)^{2f(n)} = e^{ 2f(n) \ln \left(1-\left(1-\frac1n\right)^{f(n)}\right) } = e^{ 2n g(n) \ln \left(1-\left(1-\frac1n\right)^{n g(n)}\right) }. $$ Let's break it down. $$ \left(1-\frac1n\right)^{n g(n)} = e^{g(n)\cdot n \ln\left(1-\frac1n\right) } = e^{g(n) (-1+o(1)) } \xrightarrow[n\to\infty]{} 0 $$ since $g(n)\to\infty$. Therefore, we can use the Taylor expansion of $\ln$ to get: $$ 2n g(n) \ln \left(1-\left(1-\frac1n\right)^{n g(n)}\right) = - 2n g(n) \left(1-\frac1n\right)^{n g(n)} = - 2n g(n)e^{-g(n) (1+o(1)) } $$ This gives us some intuition. This can go, depending on $g(n)$, to either $0$, $-\infty$, or basically any constant $c<0$.
For instance, take
$g(n) = \ln n$: then $- 2n g(n)e^{-g(n) (1+o(1)) } = -2(1+o(1))\ln n\xrightarrow[n\to\infty]{} -\infty$, and the overall limit will be $0$. (After taking the exponential).
$g(n) = 2\ln n$: then $- 2n g(n)e^{-g(n) (1+o(1)) } = -2(1+o(1))\frac{\ln n}{n}\xrightarrow[n\to\infty]{} 0$, and the overall limit will be $e^0=1$.
$g(n) = \ln n + \ln \ln n$: then one can check (being a bit more careful in the above, that is in the $o(1)$ term) that $2n g(n) \ln \left(1-\left(1-\frac1n\right)^{n g(n)}\right)\xrightarrow[n\to\infty]{} -2$, and the overall limit will be $e^{-2}$.
Clement C.
- 67,323
-
I don't understand what you mean by the above "$c [...]$ we have [...]." If the quantity $2n g(n) \ln \left(1-\left(1-\frac1n\right)^{n g(n)}\right)$ converges to $c$, then the original quantity converges to $e^c$. – Clement C. Jul 13 '16 at 02:27
-
$\alpha\in(0,1]$ and $g(n)=\alpha\ln n$ we have $-2ng(n)e^{-g(n)(1+o(1))}\rightarrow-\infty$ and $\alpha\in(1,\infty]$ and $g(n)=\alpha\ln n$ we have $-2ng(n)e^{-g(n)(1+o(1))}\rightarrow0$. How do you get any constant (I see $e^{-2}$ but its not clear). – Turbo Jul 13 '16 at 02:27
-
Consider $g(n)=\alpha\ln n +\beta\ln\ln n$ where $\alpha,\beta>0$ then what do we get? – Turbo Jul 13 '16 at 02:29
-
I do not see how $2n g(n)\ln\left(1-\left(1-\frac1n\right)^{n g(n)}\right)$ can converge to any desired $c>0$. I see only $-\infty$, $-2$ and $0$. – Turbo Jul 13 '16 at 02:35
-
@Turbo Try with $g(n) = \ln n + \ln\ln n +a$ for any constant $a$ of your choosing.. The limit will be $-e^{-a}$. – Clement C. Jul 13 '16 at 02:36
-
-
-
@Turbo: not really the topic here, but [the text](the link) is the syntax. – Clement C. Jul 13 '16 at 02:48
1
The first thing that comes to mind is to take a logarithm of the expression you need to find the limit of: $$ 2 f(n) \ln \left[ 1 - \left( 1 - {1 \over n} \right)^{f(n)} \right]. $$ We now want to estimate (the existence of) the limit of $$ \left( 1 - {1 \over n} \right)^{f(n)}. $$ Write $$ \left( 1 - {1 \over n} \right)^{f(n)} = \left\{ \left( 1 - {1 \over n} \right)^{n} \right\}^{f(n)/n} $$ and take the logarithm once again: $$ ({f(n)/n}) \ln \left\{ \left( 1 - {1 \over n} \right)^{n} \right\} $$ As $n \rightarrow \infty$, the latter logarithm tends to a definite limit (-1), and the ratio $({f(n)/n})$ to infinity (since we are told that $f(n)$ grows faster than $n$.
avs
- 6,276
-
1You forget to then undo taking the logarithm. You need to place your answer into e^x in order to undo your calculation. – user64742 Jul 13 '16 at 01:32
-
1I don't forget.:) I just gave some of the process, hoping to get the Asker started. – avs Jul 13 '16 at 02:03
-
Once you have the limit of $\left(1+\frac{1}{n}\right)^{f(n)}$ (it's $0$), this still doesn't say anything about the limit of the whole expression, though -- it still could be (almost) anything. – Clement C. Jul 13 '16 at 02:09
-
Should have thought it through, but didn't have time. All I wanted was to indicate to use the interplay between the logarithm and the exponential. Should have limited myself to that. – avs Jul 13 '16 at 02:34
-
@avs Agreed about the "interplay" -- that definitely the natural thing to start with! – Clement C. Jul 13 '16 at 02:58