Challenge Level

Congratulations to Federico Poloni from Casirate d'Adda (Italy) for the following solution.

Prove that $(1 + \frac{1}{n})^n \leq e < 3$.

Using Newton's formula (also called the Binomial Theorem) $$\eqalign{ \left(1 + \frac {1}{n}\right)^n &=& 1 + n\left(\frac{1}{n}\right) + \frac{n(n-1)}{2!}\left(\frac{1}{n^2}\right) + \frac{n(n-1)(n-2)}{3!}\left(\frac{1}{n^3}\right)+ \cdots \\ &\leq & 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \cdots \\ &\leq & e < 3. }$$ (a) Which is larger: $1.000001^{1000000}$ or $2$?

It's possible to prove that every number in the form $(1+\frac{1}{a})^a$ is greater than $2$. \[\left(1+\frac{1}{a}\right)^a = 1+a\cdot \frac{1}{a}+\mbox{other positive terms}> 2\] for every integer $a> 2$. For $a=1000000$, the problem is solved.

(b) Which is larger: $100^{300}$or $300!$ (i.e. $300$ factorial)?

This is a bit more complex. I'll use the formula $(1+ \frac{1}{n})^n = (\frac{n+1}{n})^n < 3 \quad (1)$

I will now use the last inequality to prove by induction that $ n!> (\frac{n}{3})^n.$ Clearly this is true for $n=1$ and $2$ and so using the induction hypothesis that it is true for $n$:

$(n+1)! = (n+1)n!
\leq(n+1)\left(\frac{n}{3}\right)^n$

$=
3\left(\frac{n+1}{3}\right)^{n+1} \left(\frac{n}{n +
1}\right)^n$.

So using (1) gives: $$ (n+1)! \leq \left(\frac{n+1}{3}\right)^{n+1}.$$ The demonstration by induction is complete. In particular, for $n=300$, the formula solves the given problem.