How prove $\lim_{n\to \infty}\frac{n}{\ln{(\ln{n}})}\left(1-a_{n}-\frac{n}{\ln{n}}\right)=-1$?

Question

Let equation $x^n+x=1$ have positive root $a_{n}$.

Show that $$\lim_{n\to \infty}\frac{n}{\ln{(\ln{n}})}\left(1-a_{n}-\dfrac{n}{\ln{n}}\right)=-1$$

some hours ago,it prove that $$\lim_{n\to \infty}\frac{n}{\ln{n}}(1-a_{n})=1$$

How prove this limit $\displaystyle\lim_{n\to \infty}\frac{n}{\ln{n}}(1-a_{n})=1$

this problem is from china paper(1993):http://www.cnki.com.cn/Article/CJFDTotal-YEKJ199301013.htm

and this paper poof is very ugly,so I want see other nice methods,I kown these can use Incremental estimation analysis,Thank you

Answer 1

Let's first set $x = 1 - y$, so that we're looking for the positive zero of

$$ p(y) = (1-y)^n - y. $$

We know from your previous questions that $y \sim \frac{\log n}{n}$ as $n \to \infty$, so that

$$ \begin{align} (1-y)^n &= \exp\left[n \log(1-y)\right] \\ &= \exp\left[-ny + O\left(\frac{(\log n)^2}{n}\right)\right] \\ &= e^{-ny} \left[1 + O\left(\frac{(\log n)^2}{n}\right)\right]. \tag{1} \end{align} $$

We conclude from this that $e^{ny}(1-y)^n$ is almost $1$ when $n$ is large, so we might guess that the solution of the equation

$$ (1-y)^n - y = 0 $$

behaves a lot like the solution of the equation

$$ e^{-ny} - y = 0 \tag{2} $$

when $n$ is large. In fact $(2)$ has an explicit solution in terms of the Lambert $W$ function: $y = W(n)/n$, and this is approximately $\log(n)/n - \log\log(n)/n$. Now let's try to quantify what "behaves a lot like" means in this particular instance.

The equation

$$ \lambda e^{-ny} - y = 0 $$

has a solution

$$ y = \frac{W(\lambda n)}{n}, $$

so by taking $\lambda = e^{ny}(1-y)^n$ we see that the equation

$$ e^{-ny}\Bigl[e^{ny}(1-y)^n\Bigr] - y = 0 $$

has an implicit solution

$$ y = \frac{W\Bigl[n e^{ny}(1-y)^n\Bigr]}{n}. \tag{3} $$

We'll need two facts here. First, it is a consequence of $(1)$ that

$$ n e^{ny}(1-y)^n = n + O(\log n)^2. $$

Second, it is a consequence of my answer here that

$$ W(x) = \log x - \log\log x + O\left(\frac{\log\log x}{\log x}\right) \tag{4} $$

as $x \to \infty$. It follows that

$$ \begin{align} &W\Bigl[n e^{ny}(1-y)^n\Bigr] \\ &\quad= W\Bigl[n + O(\log n)^2\Bigr] \\ &\quad= \log\Bigl[n + O(\log n)^2\Bigr] - \log\log\Bigl[n + O(\log n)^2\Bigr] + O\left(\frac{\log\log\Bigl[n + O(\log n)^2\Bigr]}{\log\Bigl[n + O(\log n)^2\Bigr]}\right). \end{align} $$

We calculate

$$ \begin{align} \log\Bigl[n + O(\log n)^2\Bigr] &= \log n + \log\left[1 + O\left(\frac{(\log n)^2}{n}\right)\right] \\ &= \log n + O\left(\frac{(\log n)^2}{n}\right) \end{align} $$

and similarly

$$ \log\log\Bigl[n + O(\log n)^2\Bigr] = \log\log n + O\left(\frac{\log n}{n}\right), $$

so that

$$ W\Bigl[n e^{ny}(1-y)^n\Bigr] = \log n - \log\log n + O\left(\frac{\log\log n}{\log n}\right). $$

Substituting this into $(3)$ yields

$$ y = \frac{\log n}{n} - \frac{\log\log n}{n} + O\left(\frac{\log\log n}{n\log n}\right), $$

so that

$$ a_n = 1 - \frac{\log n}{n} + \frac{\log\log n}{n} + O\left(\frac{\log\log n}{n\log n}\right). $$

We can rearrange this to see that

$$ \frac{n}{\log\log n}\left(1 - a_n - \frac{\log n}{n}\right) = -1 + O\left(\frac{1}{\log n}\right). $$

---

In fact it can be shown that $W\Bigl[n + O(\log n)^2\Bigr]$ shares the same asymptotic expansion with $W(n)$, and we can therefore find as many terms as we like of the asymptotic expansion for $a_n$. For example,

$$ a_n = 1 - \frac{1}{n}\left(L_1 - L_2 + \frac{L_2}{L_1} + \frac{(-2 + L_2)L_2}{L_1^2} + O\left(\frac{L_2}{L_1}\right)^3\right) $$

as $n \to \infty$, where $L_1 = \log n$ and $L_2 = \log\log n$. (See equation (15) in this MathWorld article.)

Answer 2

Let $a_n=1-\frac1n(\log n)b_n$, then $(a_n)^n=1-a_n$ reads $n\log a_n=\log(1-a_n)$, that is, $$ n\log\left(1-\frac1n(\log n)b_n\right)=\log\left(\frac1n(\log n)b_n\right). $$ Since $a_n\to1$ and $\log(1-x)=-x+O(x^2)$ when $x\to0$, $$ \log\left(1-\frac1n(\log n)b_n\right)=-\frac1n(\log n)b_n+o\left(\frac1n\right). $$ Since $b_n\to1$, $\log b_n=o(1)$ hence $$ -(\log n)b_n+o(1)=\log\log n-\log n+o(1) $$ that is, $$ b_n=1-\frac{\log\log n}{\log n}+o\left(\frac1{\log n}\right). $$ This means that $$ 1-a_n-\frac{\log n}n+\frac{\log\log n}n=o\left(\frac1n\right), $$ which is equivalent to $$ \frac{n}{\log\log n}\left(1-a_n-\frac{\log n}n\right)=-1+o\left(\frac1{\log\log n}\right). $$ In particular, the following weaker conclusion holds: $$ \lim_{n\to\infty}\frac{n}{\log\log n}\left(1-a_n-\frac{\log n}n\right)=-1. $$

Answer 3

I'd like to post a separate answer here in which I'll use a very different method to obtain the result. The search for this method was prompted by this comment on the previous question where the OP asks for a bound of the form $f(n) \leq a_n \leq g(n)$ with $f(n),g(n) \to 1$ as $n \to \infty$. The bound I obtained turned out to be sufficient not only for that question but for this one as well.

Some inequalities for the exponential function.

In this answer robjohn uses Bernoulli's inequality to establish the monotonicity of some familiar sequences which converge to $e$. Using this technique I'll show that

If $y$ is fixed with $0 < y < n$ then $$ \left(1-\frac{y}{n}\right)^n \text{ increases monotonically to } e^{-y} \tag{1} $$ and if $y>0$ is fixed then $$ \left(1-\frac{y}{n+y}\right)^n \text{ decreases monotonically to } e^{-y} \tag{2} $$ as $n \to \infty$.

The limits can be established in the usual way so I'll just show monotonicity.

We have

$$ \begin{align} \frac{\left(1-\frac{y}{n+1}\right)^{n+1}}{\left(1-\frac{y}{n}\right)^n} &= \left(\frac{n+1-y}{n+1}\right)^{n+1} \left(\frac{n}{n-y}\right)^n \\ &= \frac{n-y}{n} \left(\frac{n+1-y}{n+1} \cdot \frac{n}{n-y}\right)^{n+1} \\ &= \frac{n-y}{n} \left(1 + \frac{y}{(n-y)(n+1)}\right)^{n+1} \\ &> \frac{n-y}{n} \left(1 + \frac{y(n+1)}{(n-y)(n+1)}\right) \\ &= 1, \end{align} $$

proving the first statement, and

$$ \begin{align} \frac{\left(1-\frac{y}{n+y}\right)^n}{\left(1-\frac{y}{n+1+y}\right)^{n+1}} &= \left(\frac{n}{n+y}\right)^n \left(\frac{n+1+y}{n+1}\right)^{n+1} \\ &= \frac{n+y}{n} \left(\frac{n}{n+y} \cdot \frac{n+1+y}{n+1}\right)^{n+1} \\ &= \frac{n+y}{n} \left(1 - \frac{y}{(n+y)(n+1)}\right)^{n+1} \\ &> \frac{n+y}{n} \left(1 - \frac{y(n+1)}{(n+y)(n+1)}\right) \\ &= 1, \end{align} $$

proving the second.

Bounding the positive root.

Let $x$ be a root of the equation $x^n + x - 1 = 0$ with $0 < x < 1$, the existence of which is guaranteed by the intermediate value theorem. Let

$$ x = 1 - \frac{y}{n}, $$

so that $0 < y < n$. We then have

$$ \begin{align} 0 &= \left(1-\frac{y}{n}\right)^n + 1 - \frac{y}{n} - 1 \\ &= \left(1-\frac{y}{n}\right)^n - \frac{y}{n} \\ &< e^{-y} - \frac{y}{n} \end{align} $$

by $(1)$. Rearranging this gives

$$ ye^y < n $$

which implies that

$$ y < W(n) $$

and hence

$$ x > 1 - \frac{W(n)}{n}. \tag{3} $$

Similarly let

$$ x = 1 - \frac{y}{n+y} $$

so that $y>0$. We have

$$ \begin{align} 0 &= \left(1-\frac{y}{n+y}\right)^n + 1 - \frac{y}{n+y} - 1 \\ &= \left(1-\frac{y}{n+y}\right)^n - \frac{y}{n+y} \\ &> e^{-y} - \frac{y}{n+y} \end{align} $$

by $(2)$, from which we deduce that

$$ ye^y > n+y > n. $$

Thus

$$ y > W(n) $$

and so

$$ x < 1 - \frac{W(n)}{n + W(n)}. \tag{4} $$

By combining $(3)$ and $(4)$ we get

$$ 1 - \frac{W(n)}{n} < x < 1 - \frac{W(n)}{n + W(n)}. \tag{5} $$

Calculating the desired limit.

We can simplify the right-hand side of $(5)$ slightly by applying the inequality $(1+t)^{-1} \geq 1-t$, valid for $t > -1$, to get

$$ \begin{align} x &< 1 - \frac{W(n)}{n + W(n)} \\ &= 1 - \frac{W(n)}{n} \cdot \frac{1}{1 + \frac{W(n)}{n}} \\ &\leq 1 - \frac{W(n)}{n} \left(1 - \frac{W(n)}{n}\right) \\ &= 1 - \frac{W(n)}{n} + \frac{W(n)^2}{n^2}. \end{align} $$

Using this, inequality $(5)$ becomes

$$ 1 - \frac{W(n)}{n} < x < 1 - \frac{W(n)}{n} + \frac{W(n)^2}{n^2}. \tag{6} $$

Let's get a handle on the Lambert $W$ function here. In this answer I derived the inequalities

$$ \log n - \log\log n < W(n) < \log n - \log\log n - \log\left(1 - \frac{\log\log n}{\log n}\right) \tag{7} $$

and $W(n) < \log n$ which hold for $n>e$.

Substituting the first of these, the left-hand side of $(6)$ becomes

$$ \begin{align} x &> 1 - \frac{W(n)}{n} \\ &> 1 - \frac{\log n}{n} + \frac{\log\log n}{n} + \frac{\log\left(1 - \frac{\log\log n}{\log n}\right)}{n}, \end{align} $$

which rearranges to

$$ \frac{n}{\log\log n} \left(1-x-\frac{\log n}{n}\right) < -1 - \frac{\log\left(1-\frac{\log\log n}{\log n}\right)}{\log\log n}. \tag{8} $$

Mirroring this, the right-hand side of $(6)$ becomes

$$ \begin{align} x &< 1 - \frac{W(n)}{n} + \frac{W(n)^2}{n^2} \\ &< 1 - \frac{\log n}{n} + \frac{\log\log n}{n} + \frac{(\log n)^2}{n^2}, \end{align} $$

so that

$$ \frac{n}{\log\log n} \left(1-x-\frac{\log n}{n}\right) > -1 - \frac{(\log n)^2}{n \log\log n}. \tag{9} $$

Combining $(8)$ and $(9)$ yields

$$ - \frac{(\log n)^2}{n \log\log n} < \frac{n}{\log\log n} \left(1-x-\frac{\log n}{n}\right) + 1 < - \frac{\log\left(1-\frac{\log\log n}{\log n}\right)}{\log\log n}. $$

I learned this method from this answer by Qiaochu Yuan.

Answer 4

If we set $x=e^{-t}$, we get $$ x^n+x=1\iff -nt=\log\left(1-e^{-t}\right) $$ $$ \begin{align} -nt &=\log\left(1-e^{-t}\right)\\ &=\log(t)+\log\left(\frac{1-e^{-t}}{t}\right)\\ &=\log(t)-\frac{t}{2}+\log\left(\frac{\sinh(t/2)}{t/2}\right)\\ \frac12-n &=\frac{\log(t)}{t}+\frac1t\log\left(\frac{\sinh(t/2)}{t/2}\right)\tag{1} \end{align} $$ where, for $t\gt0$, $\frac1t\log\left(\frac{\sinh(t/2)}{t/2}\right)\le\min\left(\frac12,\frac{t}{24}\right)$.

On $(0,1)$ $$ \begin{align} \frac{\mathrm{d}}{\mathrm{d}t}\frac{\log(t)}{t} &=\frac{1-\log(t)}{t^2}\\ &\gt0\tag{2} \end{align} $$ therefore, $\frac{\log(t)}{t}$ monotonically increases from $-\infty$ to $0$ on $(0,1)$.

For $n\ge4$ $$ \begin{align} \frac{\log(\log(n)/n)}{\log(n)/n} &=\frac{\log(\log(n))-\log(n)}{\log(n)/n}\\ &=n\frac{\log(\log(n))}{\log(n)}-n\\ &\gt\frac12-n\tag{3} \end{align} $$ For $n\ge3$ $$ \begin{align} \frac{\log\left(\frac{\log(n)}{n}\left(1-\frac{\log(\log(n))}{\log(n)}\right)\right)}{\frac{\log(n)}{n}\left(1-\frac{\log(\log(n))}{\log(n)}\right)} &=\frac{\log(\log(n))-\log(n)+\log\left(1-\frac{\log(\log(n))}{\log(n)}\right)}{\frac{\log(n)}{n}\left(1-\frac{\log(\log(n))}{\log(n)}\right)}\\ &=-n+\frac{\log\left(1-\frac{\log(\log(n))}{\log(n)}\right)}{\frac{\log(n)}{n}\left(1-\frac{\log(\log(n))}{\log(n)}\right)}\\ &=-n-\frac{n\log(\log(n))}{\log(n)^2}\varphi\left(\frac{\log(\log(n))}{\log(n)}\right)\\ &\lt\frac12-n\tag{4} \end{align} $$ where $\varphi(u)=-\frac{\log(1-u)}{u(1-u)}\ge1$ on $(0,1)$.

Using $(1)$, $(2)$, $(3)$, and $(4)$, we can conclude that there is a $t$ that satisfies $(1)$ in the range $$ \frac{\log(n)}{n}\left(1-\frac{\log(\log(n))}{\log(n)}\right) \le t \le\frac{\log(n)}{n}\tag{5} $$ Comparing $(1)$ and $(3)$ gives $$ \begin{align} \frac{\log(\log(n)/n)}{\log(n)/n}-\frac{\log(t)}{t} &=n\frac{\log(\log(n))}{\log(n)}-\frac12+\frac1t\log\left(\frac{\sinh(t/2)}{t/2}\right)\\ &=\frac{1-\log(\xi)}{\xi^2}(\log(n)/n-t)\tag{6} \end{align} $$ for some $\xi$ between $\frac{\log(n)}{n}\left(1-\frac{\log(\log(n))}{\log(n)}\right)$ and $\frac{\log(n)}{n}$.

$(6)$ says that $$ \begin{align} \log(n)/n-t &=\frac{\xi^2}{1-\log(\xi)}\left(n\frac{\log(\log(n))}{\log(n)}-\frac12+\frac1t\log\left(\frac{\sinh(t/2)}{t/2}\right)\right)\\ &=\frac{\log(\log(n))}{n}+O\left(\frac{\log(\log(n))^2}{n\log(n)}\right)\tag{7} \end{align} $$ Since $x=e^{-t}$, we have that $x=1-t+O\left(\frac{\log(n)^2}{n^2}\right)$, and therefore, $$ \frac{n}{\log(\log(n))}\left(1-x-\frac{\log(n)}{n}\right) =-1+O\left(\frac{\log(\log(n))}{\log(n)}\right)\tag{8} $$ The desired conclusion follows from $(8)$.

Note that we avoided using big-O notation until $(7)$, where it was almost necessitated by the use of the mean value theorem.

---

Closer Investigation:

Comparison of the errors in $(3)$ and $(4)$ yield that $\frac{\log(n)}{n} \left(1-\frac{\log(\log(n))}{\log(n)}\right)$ is $\log(n)$ times closer to $t$ than is $\frac{\log(n)}{n}$. Thus, interpolation yields that a more accurate estimate would be $$ t\doteq\frac{\log(n)}{n}\left(1-\frac{\log(\log(n))}{1+\log(n)}\right)\tag{9} $$ Using $(9)$, we get that $$ \frac{n}{\log(\log(n))}\left(1-x-\frac{\log(n)}{n}\right)+1 \doteq\frac1{1+\log(n)}\tag{10} $$