Proving $\frac{n^n}{e^{n-1}}<n!<\frac{(n+1)^{n+1}}{e^{n}}$ by induction for all $n> 2$.

I am trying to prove

$$\frac{n^n}{e^{n-1}}<n!<\frac{(n+1)^{n+1}}{e^{n}} \text{ for all }n > 2.$$

Here is the original source (Problem 1B, on page 12 of PDF)

Can this be proved by induction?

The base step $n=3$ is proved: $\frac {27}{e^2} < 6 < \frac{256}{e^3}$ (since $e^2 > 5$ and $e^3 < 27$, respectively).

I can assume the case for $n=k$ is true: $\frac{k^k}{e^{k-1}}<k!<\frac{(k+1)^{k+1}}{e^{k}}$.

For $n=k+1$, I am having trouble:

\begin{align} (k+1)!&=(k+1)k!\\&>(k+1)\frac{k^k}{e^{k-1}}\\&=e(k+1)\frac{k^k}{e^{k}} \end{align} Now, by graphing on a calculator, I found it true that $ek^k >(k+1)^k$ (which would complete the proof for the left inequality), but is there some way to prove this relation?

And for the other side of the inequality, I am also having some trouble: \begin{align} (k+1)!&=(k+1)k!\\&<(k+1)\frac{(k+1)^{k+1}}{e^{k}}\\&=\frac{(k+1)^{k+2}}{e^k}\\&<\frac{(k+2)^{k+2}}{e^k}. \end{align} I can't seem to obtain the $e^{k+1}$ in the denominator, needed to complete the induction proof.

Solution 1:

Let's try an inductive proof from the original inquality for $n$, let's prove for $n+1$

$$ \frac{n^n}{e^{n-1}}<n!<\frac{(n+1)^{n+1}}{e^{n}} $$

Okay, multiply both sides by $n+1$. At least the middle is correct

$$ (n+1)\frac{n^n}{e^{n-1}}<(n+1)!<\frac{(n+1)^{n+2}}{e^{n}} $$

and we have to make the left and right sides look more appropriate

$$ \left(\color{red}{\frac{n}{n+1}} \right)^\color{red}{n}\frac{(n+1)^{n+1}}{e^{n-1}}<(n+1)!<\frac{(n+2)^{n+2}}{e^{n}} \left(\color{blue}{\frac{n+1}{n+2}}\right)^{\color{blue}{n+2}} $$

Our induction is complete if we can prove two more inequalities:

$$ \frac{1}{e} < \left(\frac{n}{n+1} \right)^n \text{ and } \left(\frac{n+1}{n+2}\right)^{n+2}< \frac{1}{e}$$

These two inequalities can be combined into one and we can take reciprocals. At least it is well-known.

$$ \bigg(1 + \frac{1}{m}\bigg)^{m+1}> \mathbf{e} > \bigg(1 + \frac{1}{n} \bigg)^n $$

This is true for any $m, n \in \mathbb{N}$.

You shave off a little bit too much when you said $(k+1)^{k+2} < (k+2)^{k+2}$. Instead, you needed the more delicate:

$$ (k+1)^{k+2} < \frac{1}{e} (k+2)^{k+2} $$

Solution 2:

If you know¹ that: $$ a_n=\left(1+\frac{1}{n}\right)^n,\qquad b_n = \left(1+\frac{1}{n}\right)^{n+1}$$ give to sequences converging towards $e$, where $\{a_n\}$ is increasing while $\{b_n\}$ is decreasing, consider that:

$$ n = \prod_{k=1}^{n-1}\left(1+\frac{1}{k}\right),\tag{1} $$ so: $$ n! = \prod_{m=2}^{n} m = \prod_{m=2}^{n}\prod_{k=1}^{m-1}\left(1+\frac{1}{k}\right) = \prod_{k=1}^{n-1}\left(1+\frac{1}{k}\right)^{n-k}=\frac{n^n}{\prod_{k=1}^{n-1}\left(1+\frac{1}{k}\right)^k}\tag{2}$$ and your inequality trivially follows.

^{1) If you are not aware of such a classical result, then prove it by induction. It is rather easy.}

Solution 3:

Proof: We will prove the inequality by induction. Since $e^2 > 5$ and $e^3 < 27$, we have $$\frac {27}{e^2} < 6 < \frac{256}{e^3}.$$ Thus, the statement for $n=3$ is true. The base step is complete.

For the induction step, we assume the statement is true for $n=k$. That is, assume $$\frac{k^k}{e^{k-1}}<k!<\frac{(k+1)^{k+1}}{e^{k}}.$$

We want to prove that the statement is true for $n=k+1$. It is straightforward to see for all $k > 2$ that $\left(1+\frac 1k \right)^k < e < \left(1+\frac 1k \right)^{k+1}$; this algebraically implies $$\left(\frac k{k+1} \right)^{k+1} < \frac 1e < \left(\frac k{k+1} \right)^k. \tag{$*$}$$ A separate induction proof for the left inequality of $(*)$ establishes $\left(\frac{k+1}{k+2} \right)^{k+2}<\frac 1e$. We now have \begin{align} (k+1)! &= (k+1)k! \\ &< (k+1) \frac{(k+1)^{k+1}}{e^k} \\ &= \frac{(k+1)^{k+2}}{e^k} \\ &= \frac{(k+1)^{k+2}}{e^k} \left( \frac{k+2}{k+2} \right)^{k+2} \\ &= \frac{(k+2)^{k+2}}{e^k} \left( \frac{k+1}{k+2} \right)^{k+2} \\ &< \frac{(k+2)^{k+2}}{e^k} \frac 1e \\ &= \frac{(k+2)^{k+2}}{e^{k+1}} \end{align} and \begin{align} (k+1)! &= (k+1)k! \\ &> (k+1) \frac{k^k}{e^{k-1}} \\ &= (k+1) \frac{k^k}{e^{k-1}} \left(\frac{k+1}{k+1} \right)^k \\ &= \frac{(k+1)^{k+1}}{e^{k-1}} \left( \frac k{k+1} \right)^k \\ &> \frac{(k+1)^{k+1}}{e^{k-1}} \frac 1e \\ &= \frac{(k+1)^{k+1}}{e^k}. \end{align} We have established that the statement $$\frac{(k+1)^{k+1}}{e^k}<(k+1)!<\frac{(k+2)^{k+2}}{e^{k+1}}$$ for $n=k+1$ is true. This completes the proof.

Solution 4:

Some times it is easier for such an induction if we shift the sequence by one step, so the basis of the expressions is nicer for algebraic manipulations.
Let's rewrite your sequence of inequalities as
$$ \displaystyle {n! \over e}<{(n+1)^{n+1} \over e^{n+1}} < {(n+1)! \over e} <{(n+2)^{n+2} \over e^{n+2}}< {(n+2)! \over e} \tag 1 $$
and for simpler references below as $$ a_0 \quad < \quad b_0 \quad <\quad a_1 \quad <\quad b_1 \quad < \quad a_2 \tag 2$$

Then we ask: does from $a_0<b_0<a_1$ follow that $a_1<b_1<a_2$ ?

Of course $a_1 = (n+1) \cdot a_0$ and so it might be useful to define $b_0$ as a fraction in the interval of $a_0$ and $a_1$: $$ b_0 = (n+1)q_1 \cdot a_0 \text{ where } q_1<1 \tag {3.1 }$$. Consequently, define $$ b_1 = (n+2)q_2 \cdot a_1 \text{ where also } q_2<1 \tag {3.2 }$$ Here the inequality $q_2 < 1$ is not known but expected and if this can be shown by induction from $q_1$ this would solve the problem .

So we start with $$q_1 = {b_0 \over a_0 (n+1)} = {(n+1)^{n} \over e^n n! } \tag {4.1 } $$ and by the beginning of the induction we know, that this is indeed smaller than 1 so $$q_1 < 1 \tag {4.2 }$$

Now we have simply $$q_2 = {b_1 \over a_1 (n+2)} = {(n+2)^{n+1} \over e^{n+1} (n+1)! } \tag {4.3 }$$ Next we consider the systematic progression in the sequence of $q_1,q_2,q_3,...$. To begin we determine the ratio $r_2={q_2 \over q_1}$ . We find $$ \begin{eqnarray} r_2&=&{q_2 \over q_1}& =&{ {(n+2)^{n+1} \over e^{n+1} (n+1)! } \over {(n+1)^{n} \over e^{n} (n)! } } \\ &&&=& {(n+2)^{n+1} e^{n} (n)! \over e^{n+1} (n+1)! (n+1)^{n}} \\ &&&=& {(n+2)^{n+1} \over e (n+1)^{n+1}} \\ &&&=& \left({n+2 \over n+1}\right)^{n+1} \cdot \frac 1e \\ r_2&=&{q_2 \over q_1}& =& \left( 1 + {1 \over n+1} \right)^{n+1} \cdot \frac 1e \end{eqnarray} \tag {5.1 }$$

It is now needed to recognize/remember from the definition of $e$, that the last expression is smaller than 1 and that for $n \to \infty$ approximates monotonically 1.
Also we see by the expansion of the binomial-series $(1+1/x)^x=1+1+1/2+...$ in the general case that for $x>2$ this is greater than $2$ so $${2 \over e} \approx 0.73 < r_2 < 1 \tag{5.2}$$

From this we know now, that $q_2$ is not only smaller than $1$ but also smaller than $q_1$ but$q_{n+1} \to q_n$ for increasing $n$.

So we have $$ \begin{eqnarray} &q_2 &=& q_1 \cdot r_2 < q_1 < 1 \\ \to& b_1 &<& (n+2) a_1 = a_2 \\ \to &a_1 &<& b_1 <a_2 \end{eqnarray} \tag {6 }$$ which we wanted to show.