Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
Not appropriate for MO - read FAQ –  Anthony Quas Apr 7 '11 at 14:36
add comment

4 Answers

up vote 10 down vote accepted

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.

share|improve this answer
    
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 '11 at 22:58
    
Thank you! fixed. –  Pietro Majer Apr 9 '11 at 3:11
    
btw, since you appreciated the method, I added a few lines on the wiki article linked above ;-) –  Pietro Majer Apr 13 '11 at 5:49
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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 '11 at 16:37
add comment

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.

share|improve this answer
    
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 '11 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 '11 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 '11 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 '11 at 12:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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