9
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Is this from some book, exercise? Is there something you're not telling us? =) $\endgroup$
    – Pedro
    Sep 6, 2013 at 3:21
  • $\begingroup$ It seems that the definition of $a_n$ has not appeared... $\endgroup$
    – abiessu
    Sep 6, 2013 at 3:25
  • $\begingroup$ The Maple command $$asympt(solve(x^n+x = 1, x), n, 2) $$ produces $$1-\frac {{\it LambertW} \left( n \right) }{n}+O \left( n^{-2} \right) .$$ It remains to apply the asymptotic formula $LambertW(n)\sim \log(n)-\log(\log(n))$ as $n \to \infty .$ $\endgroup$
    – user64494
    Sep 6, 2013 at 6:25
  • 2
    $\begingroup$ Do you possibly mean $$ \lim_{n\to\infty}\frac{n}{\log(\log(n))} \left(1-a_{n}-\color{#C00000}{\frac{\log(n)}{n}}\right)=-1 $$ Since the root is in $(0,1)$, I don't see how the limit in the question would be possible. $\endgroup$
    – robjohn
    Oct 11, 2013 at 10:22

4 Answers 4

5
$\begingroup$

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. $$

$\endgroup$
8
  • $\begingroup$ A bit of argument would be useful to justify that $a_n\to1$. For example, $a_n<1$ or else $a_n^n+a_n\ge2$ and $a_n\gt1-\frac1{\sqrt{n}}$ or else two applications of Bernoulli's Inequality would give $$ \begin{align} \left(1-\frac1{\sqrt{n}}\right)^n+\left(1-\frac1{\sqrt{n}}\right) &\le e^{-\sqrt{n}}+\left(1-\frac1{\sqrt{n}}\right)\\ &\le\frac1{1+\sqrt{n}}+\left(1-\frac1{\sqrt{n}}\right)\\ &=1-\frac1{n+\sqrt{n}}\\ &\lt1 \end{align} $$ $\endgroup$
    – robjohn
    Oct 12, 2013 at 23:10
  • $\begingroup$ How do you justify that $b_n\to1$ ? $\endgroup$
    – robjohn
    Oct 12, 2013 at 23:10
  • $\begingroup$ In the second equation, to get an error of $o\left(\frac1n\right)$, it would seem you are assuming $\log(n)b_n=o(1)$. $\endgroup$
    – robjohn
    Oct 12, 2013 at 23:23
  • $\begingroup$ @robjohn Sure one can wax on at length on the fact that $a_n\to1$ and that $b_n\to1$... except that these are already proved on the other page the OP refers to. I chose to concentrate on the interesting parts of the proof. $\endgroup$
    – Did
    Oct 13, 2013 at 7:35
  • $\begingroup$ @robjohn "In the second equation..." Wrong, $b_n=O(1)$ is already more than needed. Do you know the meaning of Landau's small-o? $\endgroup$
    – Did
    Oct 13, 2013 at 7:37
5
$\begingroup$

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} $$

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.)

$\endgroup$

You must log in to answer this question.

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