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$
5
  • 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
    Commented May 31, 2013 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
    Commented May 31, 2013 at 20:47
  • $\begingroup$ @BryanUrízar Except when $\epsilon$ is close to $0$, that's not true. $\endgroup$
    – Thomas Andrews
    Commented May 31, 2013 at 20:57
  • $\begingroup$ Ah you're right. What am I thinking.. $\endgroup$
    – user70962
    Commented May 31, 2013 at 21:00
  • $\begingroup$ Too many good answers - I guess thats a good problem to have :) $\endgroup$
    – TCSGrad
    Commented Jun 1, 2013 at 1:34

3 Answers 3

Reset to default
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$
4
  • $\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
    Commented May 31, 2013 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
    Commented May 31, 2013 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
    Commented Jun 1, 2013 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
    Commented Jun 1, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .