MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Root estimation

What is the estimation for the positive root of the following equation $$ax^k = (x+1)^{k-1}$$ where $a > 0$ (specifically $0 < a \leq 1$).

Could you point out some reference related to the question?

-
Not appropriate for MO - read FAQ – Anthony Quas Apr 7 2011 at 14:36

If we write the equation as $ax= (1+1/x)^{k-1}$ it is clear that there is exactly one positive solution (here and below I assume that $k$ is a real number larger than 1).

I. With the substitution $u=1/x$ the equation writes $a=u(1+u)^{k-1}$, and the RHS has a formal series inverse at $0$. The Lagrange inversion formula provides the (Laurent) expansion at $0$ of any integer power of the latter, in particular, of its reciprocal. One finds
$$x=a^{-1}+(k-1)+ \sum_{n=1}^\infty {(-1)^n \over n} {nk \choose n+1} a^n\ ,$$ according with the first terms found by Robert Israel. This series has a radius of convergence $k^{-k}(k-1)^{k-1}$, so it gives the positive solution of the initial equation provided $a < k ^ {-k}(k-1) ^ {k-1}$. Moreover the terms of the series are eventually decreasing in absolute value, which implies that the $n$-th partial sums are eventually a bound on $x$ alternately from above and from below. If needed, one may also estimate the remainder from the partial sums using bounds on the binomial coefficients.

II.  For large positive values of $a$, we can write the equation in the form $$a^{-\frac{1}{k}}=x(1+x)^{-1+\frac{1}{k} } \ .$$ Again, the Lagrange inversion formula provides a power series expansion of the inverse of the RHS; computing the radius of convergence this time we find $k (k-1)^{\frac{1}{k}-1 }$. Hence, evaluating that inverse at $a^{-\frac{1}{k}}$ we get $$x=\sum_{n=1}^\infty {1\over n}{\frac{n(k-1)}{k} \choose n-1 }a^{-{n\over k}}\ ,$$ converging for $a>k^{-k}(k-1)^{k-1}$. Again, estimates on the convergence are available with a little more work on the binomial coefficients. For $a=1/2$ and $k=5$, the first $20$ terms of the series sum to $x=4.4786$; compare with the numerical solution in Aleksey Pichugin's answer below.)

III. It remains the case $a := k^{-k} (k-1)^{k-1}$, though it should be covered as a limit case by the above series.

-
 This is a very efficient method of generating formal power series, thank you for sharing. I was so fixed on the expansion of first type, could not see the other option. Just a small comment: could you please replace the sum variable: should be $n$, not $k$ (I was struggling with this notation too!). – Aleksey Pichugin Apr 8 2011 at 22:58 Thank you! fixed. – Pietro Majer Apr 9 2011 at 3:11 btw, since you appreciated the method, I added a few lines on the wiki article linked above ;-) – Pietro Majer Apr 13 2011 at 5:49

Write this as $1 = t (1 + at)^{k-1}$ where $t = 1/(ax)$. The positive solution $t$ can be written as a Taylor series in $a$: according to Maple,

t = 1+(-k+1)a+1/2(3*k-2)*(k-1)a^2+(-1/3(k-1)*(4*k-3)*(2*k-1))a^3+1/24(k-1)*(5*k-4)*(5*k-3)*(5*k-2)a^4+(-1/10(6*k-5)(k-1)(3*k-1)*(2*k-1)*(3*k-2))*a^5+O(a^6)

so that

$x = a^{-1}+(k-1)- \frac{k(k-1)}{2} a+\frac{k(2k-1)(k-1)}{3} a^2 - \frac{k(k-1)(3k-1)(3k-2)}{8} a^3+\frac{k(k-1)(4k-3)(2k-1)(4k-1)}{15} a^4+O(a^5)$

As for estimates: I think you'll find $1/a \le x \le 1/a + k - 1$ assuming $k > 1$.

-
 Your estimation is correct, but I think we can do better. For example, if $a = 1$ then a good estimation of $x$ is $\Theta(k/\log k)$. Let $a$ is a fix constant, what is the best estimation for $x$ as a function of $k$ (of course, for $k$ large) – ogn Apr 7 2011 at 16:37

When $k$ is very large and $x$ is large (based on the answers from Robert Israel and Pietro Majer I think we can say that each being large requires the other to be not too small), then $(1+1/x)^{k-1}\sim e^{(k-1)/x}$ and we have to approximately solve $a = (1/x) e^{(k-1)/x}$.

$$a(k-1)=\frac{k-1}{x} e^{(k-1)/x}$$ $$(k-1)/x = W\left(a(k-1)\right)$$ $$x = \frac{k-1}{W\left(a(k-1)\right)}$$

Where $W(\cdot)$ is the Lambert W-Function.

-
 Your estimation is correct. We can take an estimation $W(ak) = \Theta(\log(ak))$ and deduce $x = \Theta(k/\log(ak))$. However, I am wondering what happens if $a$ is a function of $k$, let say $a = 2^{-k}$. In this case $\log(ak)$ is negative, but there exits a positive root. – ogn Apr 8 2011 at 11:43 @ogn, no, you cannot say that $W(ak)\sim \ln(ak)$, this expansion is only valid for large arguments. For small $a$ you should use the Taylor expansion for W instead. To the leading order you'll get $x\sim(k-1)/[a(k-1)]=1/a$. – Aleksey Pichugin Apr 8 2011 at 12:00 Put $y = ax$, we have $(ax)^n = (ax + a)^{n-1} \leq (ax + 1)^{n-1}$. Thus, $x \leq c \cdot \frac{n}{a \log n}$ for some constant $c$. % However, I think the bound could be strengthened. – ogn Apr 8 2011 at 12:05 @ogn, I did not try to argue that Zander's approximation is uniform, I only commented on your estimate. – Aleksey Pichugin Apr 8 2011 at 12:24

The presented Laurent series solutions are not very useful in practice because their radius of convergence is vanishingly small even for moderately large values of $k$. For example, as shown by Pietro Majer, the radius of convergence for $k=5$ is $R_5=5^{-5}(5-1)^{5-1}\approx0.082$. It is easy to see that $R_k\sim 1/k$ for $k\gg 1$, hence the series cannot be used for a fixed $0$ < $a\le 1$ and $k\gg1$.

Let us introduce new variable $z$ such that $x=z^{1/k}/(1-z^{1/k}).$ It transforms the original equation into the more convenient form $$az=1-z^{1/k}. \qquad (0)$$ It is known that $$z^{1/k}=1+\frac{\ln z}{k}+\frac{\ln^2 z}{2k^2}+O(1/k^3). \qquad (1)$$ If we were to leave the first two terms of this expansion, we end up with the equation $$az\approx-\frac{\ln z}{k},$$ soluble in terms of the Lambert W function, with resulting $z\approx W(ak)/(ak).$ The corresponding formula for $x$ $$x\approx \frac{ (W(ak)/(ak))^{1/k} }{ 1-(W(ak)/ak)^{1/k} } \qquad (2)$$ is less accurate than Zander's approximation for smaller $k$, where $(k+1)/x$ is small(-ish), but is more accurate for larger $k$.

Approximation (2) was obtained by truncating expansion (1) at $O(1/k)$. To improve the accuracy, the $O(1/k^2)$ term needs to be taken into the account. However, the resulting equation $$az\approx-\frac{\ln z}{k}-\frac{\ln^2 z}{2k^2},$$ cannot be solved just as easily. Hence, we replace the value of $z$ within the $O(1/k^2)$ term by its leading order value and solve $$az\approx-\frac{\ln z}{k}-\frac{\ln^2 (W(ak)/(ak))}{2k^2}$$ instead. This can again be done, somewhat tediously, in terms of Lambert's function to find that $$x\approx \frac{ (W(ak/C)/(ak))^{1/k} }{ 1-(W(ak/C)/ak)^{1/k} }, \quad C=\exp\left[ \frac{1}{2k}\ln^2\left(\frac{W(ak)}{ak}\right) \right]. \qquad (3)$$

Take $a=1/2$ and $k=5$; the numerical solution gives $x=4.4786$. Zander's formula gives $x=4.6915$. Formula (2) gives $x=4.7320$. Formula (3) gives $x=4.4867$. Things get better as $k$ increases.

ADDED 9/4/2011: It is fairly easy to construct the recurrent formulae that refine the described approximation to any desired accuracy. This is done by writing the natural logarithm of equation (0) as: $$\frac{1}{z}\ln\frac{1}{z}=ak\sum_{n=1}^{\infty}\frac{(az)^{n-1}}{n}.$$ The solution procedure is very similar to what was described before. To the leading order $$\sum_{n=1}^{\infty}\frac{(az)^{n-1}}{n}\approx \chi_1\equiv\sum_{n=1}^{1}\frac{(az)^{n-1}}{n}=1,$$ so that $$\frac{1}{z_1}\ln\frac{1}{z_1}=ak\chi_1, \quad\mbox{and}\quad z_1=\frac{W(ak\chi_1)}{ak\chi_1}.$$ Given $z_1$ one can now retain two terms of the series: $$\sum_{n=1}^{\infty}\frac{(az)^{n-1}}{n}\approx \chi_2\equiv\sum_{n=1}^{2}\frac{(az_1)^{n-1}}{n}=\sum_{n=1}^{2}\frac{W(ak\chi_1)^{n-1}}{n(k\chi_1)^{n-1}},$$ with the result $$\frac{1}{z_2}\ln\frac{1}{z_2}=ak\chi_2, \quad\mbox{and}\quad z_2=\frac{W(ak\chi_2)}{ak\chi_2}.$$ Therefore, we obtain a sequence of approximations $$x_m=\frac{[W(ak\chi_m)/(ak\chi_m)]^{1/k}}{1-[W(ak\chi_m)/(ak\chi_m)]^{1/k}}, \quad \chi_m=\sum_{n=1}^{m}\frac{W(ak\chi_{m-1})^{n-1}}{n(k\chi_{m-1})^{n-1}}, \quad \chi_1=1.$$

It is, perhaps, worth noting that the main benefits of using a relatively "expensive" approximation, such as the one given above, are in its very quick convergence and in its uniformity with respect to the parameter $a$. Nevertheless, the power series expansions, given by Pietro Majer, may be better suited for the efficient numerical implementation.

-