5

My specific problem:

For fixed $x\in(0,1),$ I would like to know how large $n$ has to be in terms of $x$ so that $n(1-x)^{n-2}\leq \tfrac{1}{5}.$ Since $\displaystyle\lim_{n\rightarrow\infty}n(1-x)^{n-2}=0$ this must eventually be true.

I think that this can be accomplished using some upper bound on $n(1-x)^n$ but I haven't found any that are tight enough. For example, the bound $(1-x)^n\leq \frac{1}{1+nx}$ won't help here. Thanks in advance for your help!

Lucas
  • 99

2 Answers2

4

Set $y=1-x$ and solve $ny^{n-2}=\frac{1}{5}\,$ for $n.$ A solution in terms of LambertW is $$n = \frac{W_0(\frac{1}{5}y^2\ln y)}{\ln y}.$$ Example $x=0.75$, then $n > 0.01272241834262.$ Check: with $n_1=0.0127\,$ you get $n_1(1-x)^{n_1-2} \approx 0.19965\,$ and with $n_2=0.0128\,$ the numbers are $n_2(1-x)^{n_2-2} \approx 0.20120$

Edit: The other real branch $W_{-1}$ will give an upper bound for $n$ with the value $n\approx 4.1953616\,$ for the example $x=0.75.\,$ Check: with $n_3=4.195$ you have $n_3(1-x)^{n_3-2} \approx 0.200083\,$ and with $n_4==4.196$ you get $n_4(1-x)^{n_4-2} \approx 0.199853$

gammatester
  • 18,827
3

First of all, there is really no reason to have the $1-x$, you can do everything again with $n y^n$, since $f(x)=1-x$ is a bijection from $(0,1)$ to itself.

Now to have $y^n < \delta$, it is enough to have $n>\frac{\ln(\delta)}{\ln(y)}$. You need $\delta=\varepsilon/n$. So you in principle need $n>\frac{\ln(\varepsilon) - \ln(n)}{\ln(y)}$. The tight solution to this involves the Lambert W function.

However, we can give an answer which is not tight in terms of elementary functions. As a side lemma, prove that $n^{1/2}>\ln(n)$. (This isn't hard: the minimum of $n^{1/2}-\ln(n)$ occurs at $n=4$, and so it is enough to prove $2>\ln(4)$, which is the same as proving $e>2$.) Then by replacing the $\ln(n)$ with $n^{1/2}$, it is enough to take $n$ larger than all solutions to

$$x+\frac{x^{1/2}}{\ln(y)}-\frac{\ln(\varepsilon)}{\ln(y)}=0.$$

The largest solution is

$$x=\left ( \frac{1}{2} \left ( -\frac{1}{\ln(y)} + \left ( \frac{1}{\ln(y)^2}+\frac{4\ln(\varepsilon)}{\ln(y)} \right )^{1/2} \right )\right )^2.$$

Note that everything is sensibly defined provided $0<\varepsilon,y<1$. For a sanity check, if $\varepsilon$ is so small that the middle term is negligible, then we get essentially $\frac{\ln(\varepsilon)}{\ln(y)}$ as expected. (I made an error that failed this check earlier.)

Ian
  • 101,645
  • I like this approach but I fail to see why the equation $x+\frac{x^{1/2}}{\ln y}-\frac{\ln \varepsilon}{\ln y}=0$ has a unique solution. I think that it has two solutions. – Lucas Jul 21 '15 at 16:09
  • @Lucas I forgot that $\ln(y)<0$, so $x+\frac{x^{1/2}}{\ln(y)}$ is not monotone. Thinking that it was, I thought the uniqueness was obvious, but you are right that it is not. In this case it comes down to whether $\frac{-1}{\ln(y)}-\left ( \frac{1}{\ln(y)^2}+\frac{4 \ln(\varepsilon)}{\ln(y)} \right )^{1/2} >0$. But in fact, if $0<\varepsilon,y<1$, this quantity is negative, so there is only one solution in this regime. That's because, if you neglect the second term in the square root, you get $0$, and the second term in the square root is positive, so it only makes the overall quantity smaller. – Ian Jul 21 '15 at 16:18
  • @Lucas Note that $z^2+\frac{z}{\ln(y)} - \frac{\ln(\varepsilon)}{\ln(y)}=0$ does have two solutions in $z$ for $0<\varepsilon,y<1$. But one of them is negative, so it isn't the square root of anything. I still edited accordingly, because the uniqueness is not really important (the important matter is that $n$ be larger than all of them; the fact that "all" is actually "one" is not important). – Ian Jul 21 '15 at 16:21
  • I see. Thanks. I am working on a slight modification of the problem you have solved as I have $n-2$ in the exponent instead of $n$ and this variation gives two distinct real solutions; but as you said, all that matters is that $n$ is larger than all of the solutions. – Lucas Jul 21 '15 at 16:29
  • @Lucas Oh, I missed the $n-2$. That actually is no obstacle, as far as I can tell. Note that $n y^{n-2}<\varepsilon$ is equivalent to $ny^n < y^2 \varepsilon$, and then note that $y^2 \varepsilon$ is still less than $1$ provided $\varepsilon$ is less than $1$. So replace my $\varepsilon$ with $y^2 \varepsilon$ to get the result you want. – Ian Jul 21 '15 at 16:40