1

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?$

liedora
  • 87
  • Could you differentiate the equation? –  Feb 08 '14 at 02:55
  • 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}$ – Alex Feb 08 '14 at 04:08
  • Is induction mandatory? The proof of the LHS inequality, for example, is direct without induction and quite uneasy to fit into one. – Did Feb 09 '14 at 08:55
  • Indeed, induction is required - the question is from an induction chapter in a number theory text :) – liedora Feb 09 '14 at 09:24

1 Answers1

0

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

Jack D'Aurizio
  • 353,855