2
$\begingroup$

How to prove/show $1- (\frac{2}{3})^{\epsilon} \geq \frac{\epsilon}{4}$, given $0 \leq \epsilon \leq 1$?

I found the inequality while reading a TCS paper, where this inequality was taken as a fact while proving some theorems. I'm not a math major, and I'm not as sufficiently fluent in proving inequalities such as these (as I would like to be), hence I'd like to know, why this is true (it does hold for a range of values of $\epsilon$ from $0$ to $1$), and how to go about proving such inequalities in general.

$\endgroup$
  • 2
    $\begingroup$ A calculus approach would be: Let $f(\epsilon) = 1 - (2/3)^{\epsilon} - \epsilon/4$. Compute its derivative, find where it attains its minimum value, and show that even there it is positive. $\endgroup$ – TMM May 31 '13 at 20:45
  • $\begingroup$ @TMM: That's an interesting idea! You can make it into an answer, as it would definitely be one of the answers (and proof strategies) that I was looking for! $\endgroup$ – TCSGrad May 31 '13 at 20:47
  • $\begingroup$ @BryanUrízar Except when $\epsilon$ is close to $0$, that's not true. $\endgroup$ – Thomas Andrews May 31 '13 at 20:57
  • $\begingroup$ Ah you're right. What am I thinking.. $\endgroup$ – user70962 May 31 '13 at 21:00
  • $\begingroup$ Too many good answers - I guess thats a good problem to have :) $\endgroup$ – TCSGrad Jun 1 '13 at 1:34
3
$\begingroup$

The function $f(x) = 1 - \left( \tfrac{2}{3} \right)^x$ is increasing and concave down on the interval $[0, 1]$. One consequence of this fact is that the curve lies above the secant line connecting $(0, f(0)) = (0, 0)$ and $(1, f(1)) = (1, \tfrac{1}{3})$. This is the line $y = \tfrac{1}{3} x$, so actually the slightly stronger inequality holds for all $0 \le \epsilon \le 1$: $$ 1 - \left( \frac{2}{3} \right)^\epsilon \ge \frac{\epsilon}{3} $$ Here's a picture of the curve $y = f(x)$, the secant line $y = \tfrac{x}{3}$, and the line $y = \tfrac{x}{4}$.

Curves involved in the inequality.

$\endgroup$
  • $\begingroup$ Maybe the formatting of the result is a bit off - it looks like the brackets are around the denominator only, hence the epsilon applies only on it...I don't have edit privileges, perhaps u can fix it? The answer is great otherwise! $\endgroup$ – TCSGrad May 31 '13 at 21:14
  • $\begingroup$ Are you suggesting that you intended to ask about the inequality $1 - \frac{2}{3^\epsilon} \ge \frac{\epsilon}{4}$? $\endgroup$ – Sammy Black May 31 '13 at 21:26
  • 1
    $\begingroup$ Well, I'll be... I could swear my Chrome browser at Uni was showing the first brackets around only 3 in the denominator, in your answer - hence I wanted the edit! But, now in FireFox, its showing up correctly, hence I understand why you were confused! Bottomline: your answer is perfectly OK :) $\endgroup$ – TCSGrad Jun 1 '13 at 1:32
  • $\begingroup$ Btw, could you tell me how to get plots/figures in stackexchange answers - I presume you've a better way than generating it in Matlab/mathematica, exporting it to jpg and uploading it - is there a online graph generator that u use? $\endgroup$ – TCSGrad Jun 1 '13 at 1:33
2
$\begingroup$

Let $$f(x)=1-\left(\frac{2}{3}\right)^x$$ then $$f'(x)=-\left(\frac{2}{3}\right)^x\log\left(\frac{2}{3}\right)$$ so $f$ is a concave function on the interval $[0,1]$ since $f'$ is decreasing hence the curve of $f$ is below the tangent line at the point $(0,f(0))=(0,0)$ which has the slope $f'(0)=-\log\left(\frac{2}{3}\right)\approx0.404$ and above the secant line connecting $(0,f(0))=(0,0)$ and $(1,f(1))=(1,\frac{1}{3})$ so $$0.33x\leq f(x)\leq 0.41 x\quad \forall x\in[0,1]$$

$\endgroup$
1
$\begingroup$

On of the most helpful inequalities about the exponential is $e^t\ge 1+t$ for all $t\in\mathbb R$. Using this, $$ \left(\frac32\right)^\epsilon=e^{\epsilon\ln\frac32}\ge 1+\epsilon\ln\frac32$$ for all $\epsilon\in\mathbb R$. Under the additional assumption that $ -\frac1{\ln\frac32}\le \epsilon< 4$, multiply with $1-\frac\epsilon4$ to obtain $$\begin{align}\left(\frac32\right)^\epsilon\left(1-\frac\epsilon4\right)&\ge \left(1+\epsilon\ln\frac32\right)\left(1-\frac\epsilon4\right)\\&=1+\epsilon\left(\ln\frac32-\frac14\right)-\frac{\ln\frac32}{4}\epsilon^2\\&=1+\frac{\ln\frac32}{4}\epsilon\cdot\left(4-\frac1{\ln\frac32}-\epsilon\right).\end{align}$$ Hence $\left(\frac32\right)^\epsilon\left(1-\frac\epsilon4\right)\ge1$ and ultimately $1-\frac\epsilon4\ge \left(\frac23\right)^\epsilon$ for all $\epsilon$ with $0\le\epsilon\le 4-\frac1{\ln\frac32}\approx1.53$

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