Solution of $(1-x)^n = x$ : Rate of convergence of $x \to 0$ as $n \to \infty$?

Question

The equation $(1-x)^n = x$ has a solution in $x' \in (0,1)$ and indeed the solution $x' \to 0$ as $n \to \infty$. (Consider $f(x) = (1-x)^n$ noting that $f(0) = 1$ and $f(1) = 0$. As $n$ increases, $f(x)$ is 'flat' in an increasingly-large neighbourhood around $x=1$. Hence $f(x)$ crosses the line $y=x$ at a point that gets closer to $x=0$ as $n \to \infty$.)

What is the rate of convergence of $x' \to 0$ as $n \to \infty$?

What I have tried:

• I have obtained solutions for $x_n$ for $n = 1 \dots 17$ as shown below. (The ratio $x_{x+1}/x_n$ is increasing so it's not exponential decay (?))

• I did a quick literature look for the bounds on the real-valued roots of a polynomial On Geometry of the Zeros of a Polynomial. I was seeking an upper bound that decreases with $n$. Unfortunately, the bounds in the literature (that I found) were all $1 + something$ which is unhelpful.

Any suggestions most appreciated. Many thanks in advance.

$(1-x)^n = x$ obtained numerically">

Answer 1

Let $x_n$ be the unique solution of the equation $(1-x)^n=x$ on $(0, 1)$.

1. Let $f(x) = (1 - x)^n - x $. Then by using the inequality $1-x \leq e^{-x}$, we get $$ f(0) = 1 \qquad\text{and}\qquad f\left(\frac{\log n}{n}\right) \leq e^{-\log n} - \frac{\log n}{n} = -\frac{\log(n/e)}{n}. $$ So by the intermediate value theorem and the uniqueness of the zero, we conclude that $$ 0 < x_n < \frac{\log n}{n} \qquad\text{for}\quad n \geq 3. $$

2. Write $y_n = \log x_n$ and $\epsilon_n=-\frac{\log(1-x_n)}{x_n}-1$. Then $$ n = \frac{\log x_n}{\log(1-x_n)} = -\frac{\log x_n}{x_n(1 + \epsilon_n)}. $$ Rearranging this equation, we get $$ -y_n e^{-y_n} = n(1 + \epsilon_n). $$ This equation can be solved by using the Lambert W-function $W(x)$. This is a well-studied special function defined as the inverse of $x \mapsto xe^{x}$, Using this, $$ y_n = -W(n(1 + \epsilon_n)). $$ Then $$ x_n = e^{y_n} = e^{-W(n(1 + \epsilon_n))} = \frac{W(n(1 + \epsilon_n))}{n(1 + \epsilon_n)} $$ The previous step tells that $\epsilon_n = \mathcal{O}(\frac{\log n}{n})$, and then a bit of effort shows that: $$ x_n = \frac{W(n)}{n}\left(1+\mathcal{O}\left(\frac{\log n}{n}\right)\right). $$ The following is a comparison between $x_n$ and $W(n)/n$:

   

3. If the use of a special function sounds less attractive, one may use the known bound $$ W(x) = \log x - \log\log x + \mathcal{O}\left(\frac{\log\log x}{\log x}\right) $$ to produce a bound involving only elementary functions: $$ x_n = \frac{\log n - \log\log n}{n}\left(1 + \mathcal{O}\left(\frac{\log\log n}{(\log n)^2}\right) \right) $$

Answer 2

Then $\ln{x_n}=n\ln(1-x_n)\sim -nx_n$.

Write $x_n=e^{-y_n}$ with $y_n \rightarrow \infty$. Then, taking logarithms again, $y_n+\ln{y_n}=\ln{n}+o(1)$. Thus $y_n=(\ln{n})(1+z_n)$ with $z_n \rightarrow 0$.

It follows then that $\ln{\ln{n}}+z_n\ln{n}=o(1)$, hence $z_n=-\frac{\ln{\ln{n}}}{\ln{n}}+o((\ln{n})^{-1})$, ie $y_n=\ln{n}-\ln{\ln{n}}+o(1)$. Therefore $x_n=e^{-\ln{n}+\ln{\ln{n}}+o(1)} \sim \frac{\ln{n}}{n}$.