2
$\begingroup$

Problem

When studying Chernoff bound, one result is used without proof and reference, which is $$ (1+x)\log(1+x)-x\geq \frac{x^2}{\frac{2}{3}x+2} $$ I am wondering how this is proved.

What I Have Done

I checked the minimum of LHS and maximum of RHS, this indeed holds. But when it comes to prove this, this sort of check is far from enough.

Something I think relatable is doing some Taylor expansion of LHS, but I did not get the result.

Could someone help me, thank you in advance.

Edit

Take the second-order derivative of $f(x)=(1+x)\log(1+x)-x-\frac{x^2}{\frac{2}{3}x+2}$ gives us $f''(x)=\frac{x^2\, \left(x + 9\right)}{\left(x + 1\right)\, {\left(x + 3\right)}^3}$, which shows the correctness of the answer below.

$\endgroup$
7
  • $\begingroup$ For which $x$ is the inequality to hold? For all $x>-1$? [need at least that restriction because of $\log(1+x)$] $\endgroup$ – coffeemath Nov 18 '18 at 3:20
  • $\begingroup$ Yeah, if you solve the inequality for the log, you get that it's $\ge \dfrac{5x^2+6x}{2x^2+8x+6}$ whose limit as $x \to \infty$ is $\dfrac 52$, and since $\log$ is unbounded its easy to see that after some point the inequality must be true. $\endgroup$ – Ovi Nov 18 '18 at 3:25
  • $\begingroup$ I don't think it is always true. Take x=9 for example. You get 1 on the left and 10.125 on the right. It is only true in (-1,0]. $\endgroup$ – NoChance Nov 18 '18 at 4:45
  • $\begingroup$ @NoChance. For $x=9$, $lhs=10\log(10)-9=14.0259$ $\endgroup$ – Claude Leibovici Nov 18 '18 at 4:49
  • 1
    $\begingroup$ The rhs is the $[2,1]$ Padé approximant (built at $x=0$) of the lhs. $\endgroup$ – Claude Leibovici Nov 18 '18 at 4:54
3
$\begingroup$

Hint: Study the function $f(x) = LHS-RHS$ and show it is non-negative

Detailed hint: $f$ is infinitely differentiable on $(-1,\infty)$. Derive $f$ (twice): $f''$ is easy to handle, as it is a rational function (no more logarithms); it has a single root at $0$ and is always non-negative. This means $f'$ is non-decreasing; since $f'(0)=0$, we have $f$ decreasing on $(-1,0)$ and increasing on $(0,\infty)$. But $f(0)=0$, and thus $f(x)\geq f(0)=0$ for all $x$.

$\endgroup$
2
  • 2
    $\begingroup$ Thank you, but I think we can do this because we know RHS. I am wondering how something like RHS is derived from LHS using certain techniques. $\endgroup$ – Mr.Robot Nov 18 '18 at 5:04
  • 2
    $\begingroup$ Then you can for instance look at Taylor series to have an idea of a possible approximation by polynomials. For things like this one (not a polynomial), you would look at another type of approximation by the "best function in a simple class" (e.g., this: en.wikipedia.org/wiki/Pad%C3%A9_approximant) $\endgroup$ – Clement C. Nov 18 '18 at 6:04
0
$\begingroup$

Also, we can make the following.

We need to prove that $f(x)\geq0,$ where $$f(x)=\ln(1+x)-\frac{5x^2+6x}{2(x^2+4x+3)}.$$ We see that $$f'(x)=\frac{x^3}{(x^2+4x+3)^2},$$ which says that $$f(x)\geq f(0)=0$$ and we are done!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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