Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
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}}}.$$

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.