Crandall, Pomerance - Prime Numbers: A Computational Perspective - Exercise 6.8 at page 274

165 Views Asked by At

I am trying to solve the exercise in the title. I write it here: prove for $d,n\in \mathbb{N}$ $$\frac{3}{2}\left(\frac{d}{\ln 2}\right)^d<n\quad\Rightarrow\quad n<2\lfloor{n^{1/d}\rfloor}^d$$

I have tried to solve it in this way: $$\frac{3}{2}\left(\frac{d}{\ln 2}\right)^d<n\quad\Rightarrow\quad \frac{3^{1/d}}{2^{1/d}}\frac{d}{\ln 2}<n^{1/d}$$ so $$n<2\lfloor{n^{1/d}\rfloor}^d\quad\Leftarrow\quad n<2(n^{1/d}-1)^d\quad\Leftarrow\quad n<2\left(\frac{3^{1/d}}{2^{1/d}}\frac{d}{\ln 2}-1\right)^d $$ But this way is an impasse. Then I tried in this way $$n<2\lfloor{n^{1/d}\rfloor}^d\quad\Leftarrow\quad n<2(n^{1/d}-1)^d\quad\Leftrightarrow\quad 2\sum_{i=0}^d{\binom{d}{i}n^{(d-i)/d}(-1)^i}-n>0 $$

But I can't proceed. Could anyone give me a hint please?

1

There are 1 best solutions below

6
On BEST ANSWER

$\newcommand\R{\mathbb{R}}$Since you asked for a hint. I prefer to do just that. If you prove that the function $f:]0,1]\rightarrow \mathbb R$ defined by $$f(x)=\frac{3^x (2^x - 1)}{4^x\ln{2^x}}$$ is strictly increasing (in $]0,1]$) and show that $\displaystyle\lim_{x\to 0}f(x) = 1$ then you can solve the problem.

Edit: It's been a while since my post, but I guess I also need to provide the proof of my hint and I only got the time now to do it.

Taking the derivative and multiplying by $x^2$ (because testing positivity is not affected by this) within the interval $]0,1]$ you get $$x^2f'(x)=x\left(\left(\frac{3}{2}\right)^x\ln\frac{3}{2} - \left(\frac{3}{4}\right)^x\ln\frac{3}{4}\right) - \left(\frac{3}{4}\right)^x (2^x-1)$$

Checking positivity of the above within $]0,1]$ is similar to checking positivity of the above divided by $(3/4)^x$. So it suffices to show that $$g(x):=2^x(x\ln\frac{3}{2} -1) + 1-x\ln\frac{3}{4}$$ is positive. For me, this is not immediately seen. So we take the derivative of $g$ and obtain $$g'(x)=2^x\ln\frac{3}{2}+2^x\ln{2}(x\ln\frac{3}{2}-1)-\ln\frac{3}{4}$$

The above is clearly an increasing function for $x\in]0,1]$ and $g'(0)=0$ will be less than any $g'(a)$ for $a\in ]0,1]$ (why?). So $g$ is an increasing function. We check that $g(0)=0$ and $g(1)>1$ so $g$ takes positive values in $]0,1]$ (why?) and this implies that $f$ is increasing.