tun1ju2k1ki

2022-09-30

Tight estimate for a log-linear inequality
Given $q>0$ and $p$, how do we get a tight estimate for the smallest $x$ such that $x\mathrm{log}\left(x\right)+px\ge q$? (such an $x$ always exists).

Krista Arroyo

Consider the function
$f\left(x\right)=x\mathrm{log}\left(x\right)+px-q$
The first derivative
${f}^{\prime }\left(x\right)=\mathrm{log}\left(x\right)+1+p$
cancels at a single place $x={e}^{-\left(p+1\right)}$ and at this point the value of the function is $-\left(q+{e}^{-\left(p+1\right)}\right)$. The second derivative being always positive, then this point corresponds to a minimum.
So, the function (which is defined for $x\ge 0$) starts from $-q$, goes to a minimum and increases again. This means that the inequality
$x\mathrm{log}\left(x\right)+px\ge q$
will hold for any $x$ larger than the root of $f\left(x\right)=0$
The solution of this equation is given by
$x=\frac{q}{W\left(q\phantom{\rule{thinmathspace}{0ex}}{e}^{p}\right)}$
where appears Lambert function.
Since $q>0$, the solution is larger than ${x}_{0}={e}^{-p}$ and the first iterate of Newton method would be ${x}_{1}=q+{e}^{-p}$. But $f\left({x}_{0}\right){f}^{″}\left({x}_{0}\right)<0$ makes ${x}_{1}$ an overestimate of the solution (from Darboux theorem).
Edit
Since, in a comment, you tell that your problem is to find n such as
$\frac{{2}^{n}}{n!}<ϵ$
If ound in old notes of mine a similar problem that I adapted to your. Considering $ϵ={10}^{-k}$, I was able to find this simple correlation
$n\approx 3.45433+2.52846\phantom{\rule{thinmathspace}{0ex}}{k}^{0.746311}$
which I established for $5\le k\le 50$
So, if you want to refine more, use this as an estimate from which you start Newton method using Stirling approximation for $n!$

Do you have a similar question?