1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Not appropriate for MO - read FAQ $\endgroup$ Apr 7, 2011 at 14:36

4 Answers 4

10
$\begingroup$

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. [edit] 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.

$\endgroup$
2
  • $\begingroup$ 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!). $\endgroup$ Apr 8, 2011 at 22:58
  • $\begingroup$ btw, since you appreciated the method, I added a few lines on the wiki article linked above ;-) $\endgroup$ Apr 13, 2011 at 5:49
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – ogn
    Apr 7, 2011 at 16:37
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – ogn
    Apr 8, 2011 at 11:43
  • $\begingroup$ @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$. $\endgroup$ Apr 8, 2011 at 12:00
  • $\begingroup$ 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. $\endgroup$
    – ogn
    Apr 8, 2011 at 12:05
  • $\begingroup$ @ogn, I did not try to argue that Zander's approximation is uniform, I only commented on your estimate. $\endgroup$ Apr 8, 2011 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.