# Show $0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}$ by induction

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

-
Could you differentiate the equation? – Sanath K. Devalapurkar Feb 8 '14 at 2: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 8 '14 at 4: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 9 '14 at 8:55
Indeed, induction is required - the question is from an induction chapter in a number theory text :) – 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}}}.$$

-