Show that if $0\leq x < n, n \geq 1$, and $n\in\mathbb{N}$ then

$$ 0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}. $$

By using induction.

Progress: Decided to split the problem up into two parts, (i) and (ii).

(i) $ 0 \leq e^{-x} - \left ( 1- \frac{x}{n} \right ) ^ n $.

(i) $e^{-x} - \left ( 1- \frac{x}{n} \right ) ^ n \leq \frac{x^2e^{-x}}{n}.$

For part (i),

Base case: (n = 1)

We have

$$\begin{align} 1-x &\leq e^{-x} \\ e^{-x} +x -1 & \geq 0. \end{align}$$

Differentiating gives,

$$ \begin{align} \frac{d}{dy} \left ( e^{-x} +x -1 \right )& = -e^{-x} +1 \\ & \geq 0 \end{align}$$ for $0 \leq x <1$. Thus the function is non-decreasing on $\left[ 0,1 \right )$ which implies $e^{-x} + x -1 \geq 0 $ thus,$ 1-x \leq e^{-x}$ on the required interval. (my calc isn't very strong but I assume this is the right process to prove one function is $\geq$ another).

Induction step: Assume formula holds for some arbitrary positive integer $n=k$, that is $$0 \leq e^{-x} - \left( 1-\frac{x}{k} \right )^k$$ using this, we must now show that the formula holds for $n=k+1$, i.e.

$$ 0 \leq e^{-x} - \left ( 1- \frac{x}{k+1} \right ) ^{k+1}. $$

So how on earth do we use the induction step in get the required equation for $n=k+1?$

  • $\begingroup$ Could you differentiate the equation? $\endgroup$ – user122283 Feb 8 '14 at 2:55
  • $\begingroup$ For $n=1$ show that $f(x)=e^{-x}-1+x \geq 0$ by showing $f(0)=0$, then take a derivative and show the function is increasing for $x>0$. Then use this idea for $g(x)=e^{-x}-1+x-x^2 e^{-x}$ $\endgroup$ – Alex Feb 8 '14 at 4:08
  • $\begingroup$ Is induction mandatory? The proof of the LHS inequality, for example, is direct without induction and quite uneasy to fit into one. $\endgroup$ – Did Feb 9 '14 at 8:55
  • $\begingroup$ Indeed, induction is required - the question is from an induction chapter in a number theory text :) $\endgroup$ – liedora Feb 9 '14 at 9:24

Lemma A. If $x\geq y>0$, $$ x^n-y^n \leq n (x-y) x^{n-1}.$$

Proof: expand $\frac{x^n-y^n}{x-y}$ as a geometric sum and apply the trivial bound $y\leq x$ to each term.

Lemma B: For any $x\in\mathbb{R}$ and $n\in\mathbb{N}^+$, $$ e^{-x/n} \geq 1-\frac{x}{n}.$$

Proof: $e^{x}$ is a convex function.

Lemma C: For any $z\in[0,1]$, $$ e^{-z}-(1-z) \leq \frac{z^2}{2}.$$

Proof: $\frac{e^{-z}-(1-z)}{z}$ is a concave function on $[0,1]$.

By Lemma A, Lemma B and Lemma C it follows that:

$$ \forall n\in\mathbb{N}^+,\forall x\in[0,n],\qquad \color{red}{0\leq e^{-x}-\left(1-\frac{x}{n}\right)^n \leq \frac{x^2 e^{-x}}{2n e^{-x/n}}}.$$

| cite | improve this answer | |

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.