## Sunday, January 7, 2007

### Big. Topic: Algebra/Inequalities. Level: AIME.

Problem: (2002 Putnam - B3) Show that, for all integers $n > 1$,

$\displaystyle \frac{1}{e}-\left(1-\frac{1}{n}\right)^n < \frac{1}{ne}$. [Reworded]

Solution: First of all, this is only one of two inequalities in the problem, but it's the cooler half... yeah. We will rewrite the inequality as

$\displaystyle 1-\frac{1}{n} < e \left(1-\frac{1}{n}\right)^n$.

Using the fact that $\displaystyle \lim_{n \rightarrow \infty} \left(1+\frac{1}{n}\right)^n = e$ from below, we know

$\displaystyle e > \left(1+\frac{1}{n}\right)^n$

so

$\displaystyle e \left(1-\frac{1}{n}\right)^n > \left(1+\frac{1}{n}\right)^n \left(1-\frac{1}{n}\right)^n = \left(1-\frac{1}{n^2}\right)^n > 1-\frac{1}{n}$,

where the last step follows from the binomial expansion or the Bernoulli Inequality. And we're done. QED.

--------------------

Comment: Basically, all you really needed was to estimate $e$ somehow, so the limit form came in handy. The other inequality was showing that the LHS is $> \frac{1}{2ne}$, but the only solution that I know to that one is taking the $\log$ and expanding using the Taylor series, which isn't as cool.

--------------------

Practice Problem: The left inequality not shown here can also be written as

$\displaystyle e < \left(1+\frac{1}{n}+\frac{1}{2n(n-1)}\right)^n$.

Can you show this?