14
$\begingroup$

To Prove : $n! > (n/e)^n$

The question seems easy but it ain't; anyone up for it ?

$\endgroup$
8
  • 25
    $\begingroup$ I don't appreciate this challenging tone. You should be here in order to learn, not in order to make other people feel bad for not being able to solve problems. This is childish behavior which is not appropriate for this forum. $\endgroup$ Aug 20, 2011 at 19:46
  • 45
    $\begingroup$ I think there's a nicer way of putting that. I doubt anyone felt bad reading this question but the asker probably did reading your comment. $\endgroup$
    – Joe
    Aug 20, 2011 at 20:31
  • 12
    $\begingroup$ Anil, welcome to MSE. Whether it's childish or not, mathematicians have challenged each other to solve problems throughout the ages. In any case, I see nothing wrong with the tone of this question and anyone who's offended by it is being oversensitive in my opinion. If I felt bad every time I came across a problem I could not solve, I would be an extremely miserable person. $\endgroup$
    – LostInMath
    Aug 20, 2011 at 23:05
  • 1
    $\begingroup$ @Qiaochu What about his tone is challenging? And what about the question would make others feel bad for not being able to solve problems? $\endgroup$ Aug 21, 2011 at 12:49
  • 4
    $\begingroup$ Perhaps I overreacted. I have seen people say things like "this question seems easy but it ain't" with the intent I described but I was being too hasty in ascribing that intent to the OP. My apologies, @Anil. $\endgroup$ Aug 21, 2011 at 12:56

5 Answers 5

23
$\begingroup$

Here's a hint. You assume that $n!>\left(\frac{n}{e}\right)^n$. Now you should show it for n+1, i.e., you should show that $(n+1)! > \left(\frac{n+1}{e}\right)^{n+1}$.

You can write

\begin{equation} (n+1)! > (n+1) \left(\frac{n}{e}\right)^n = (n+1)\left(\frac{n}{n+1}\right)^n \left(\frac{(n+1)^n}{e^n}\right) \end{equation}

Can you solve it from here?

$\endgroup$
5
  • 3
    $\begingroup$ Very nicely expressed as a route to a solution! $\endgroup$ Aug 20, 2011 at 20:05
  • $\begingroup$ Hmm not sure (n/n+1)^n < 1 $\endgroup$ Aug 21, 2011 at 17:55
  • 1
    $\begingroup$ @Anil - $\left(\frac{n}{n+1}\right)^n = \frac{1}{(1+1/n)^n}$. You should know that $\lim_{x \to \infty} (1+1/x)^x = e$. If instead of using the limit, you prove the inequality $(1+1/n)^n < e$ and use it in the expression, you will get the answer. $\endgroup$
    – svenkatr
    Aug 22, 2011 at 3:44
  • $\begingroup$ Just to elaborate on svenkatr's hint - We must show $(1+1/x)^x$ is an increasing function first. Then, knowing it's limit is $e$ gives us the inequality he mentioned. $\endgroup$ Aug 22, 2011 at 9:26
  • $\begingroup$ @Ragib: Well, it depends how you define $e$ in the first place. It can be defined as $\lim_{n \to \infty}(1 + \frac{1}{n})^{n},$ after showing that that sequence is increasing, but bounded above, so converges to its least upper bound (then it's clear that this least upper bound, which we call $e$, is greater than $(1+\frac{1}{n})^{n}$ for all integers $n$). $\endgroup$ Aug 22, 2011 at 21:57
21
$\begingroup$

By considering the exponential power series we observe that for $x>0$, $$ e^x > \frac{x^n}{n!} $$ Now setting $x=n$ we obtain $$e^n > \frac{n^n}{n!} $$ which rearranges to precisely what is desired. I should note that I had first learned this incredibly short and simple proof of this fact from Qiaochu Yuan's posts on this website, and he in turn attributed it to this article written by Terence Tao.

$\endgroup$
4
  • $\begingroup$ To be accurate, it works for $x=0$. You just need to "decide" whether or not $0^0$ is of value $0,1$ or something else. If you claim it undefined then you need require that $x\cdot n\neq 0$. $\endgroup$
    – Asaf Karagila
    Aug 21, 2011 at 5:49
  • $\begingroup$ I just excluded $x=0$ for a matter of convenience. To include $x=0$ would force us to consider that for $n=0$ strict inequality no longer holds (if we take the usual convention that here $0^0=1$). $\endgroup$ Aug 21, 2011 at 7:26
  • 1
    $\begingroup$ This seems to be the "right" proof for this statement, though the title of the question (but not the body of the text), asked for a proof by induction. $\endgroup$ Aug 21, 2011 at 9:00
  • $\begingroup$ Nice proof -- Didnt think of problem in this direction -- But then again the main idea was to prove by induction $\endgroup$ Aug 21, 2011 at 18:00
4
$\begingroup$

This is the "easy" part of Stirling's formula -- the crude order of magnitude estimate showing how huge $n!$ is, without the $\sqrt{2 \pi n}$ correction that is harder to derive.

Taking logarithms, you are asking for $\log(n!) > n (\log n - 1)$. The latter is the indefinite integral of $\log(n)$. Drawing a picture, this follows from $\log(n)$ being an increasing function. The inequality compares the area under the graph of the function to the area of rectangles underneath the graph. A stronger inequality can be obtained using trapezoids and the convexity of $\log(x)$. I think you can get the $\sqrt{n}$ factor this way but not the exact constant $\sqrt{2 \pi}$.

$\endgroup$
1
  • 1
    $\begingroup$ Just to verify the last statement, it is indeed true that using trapezoids to estimate the area can give us the estimate $n! \sim C n^{n + 1/2} e^{-n} $ for some constant $C$. Then, the "hard" part is to determine $C$, which is commonly done by considering the Wallace product. $\endgroup$ Aug 21, 2011 at 3:09
3
$\begingroup$

I had originally written this up for another question but it seems fitting here as well. Maybe this can help someone.

Depending on how you introduced $e$, you might be able to use the fact that there are two sequences $(a_n)_{n \in \mathbb{N}}$, $(b_n)_{n \in \mathbb{N}}$ with

$$\begin{align} a_n ~~~&:=~~~ \left ( 1 + \frac{1}{n} \right ) ^n \\ ~ \\ b_n ~~~&:=~~~ \left ( 1 - \frac{1}{n} \right ) ^{-n} \end{align}$$

and

$$\underset{n \rightarrow \infty}{\lim} a_n ~~~=~~~ \underset{n \rightarrow \infty}{\lim} b_n ~~~=~~~ e \\ ~ \\$$

While both sequences converge to the same limit, $a_n$ approaches from the bottom and $b_n$ approaches from the top:

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import rcParams
rcParams.update({'figure.autolayout': True})

pts = np.arange(0, 20, 1)
a_n = lambda n: (1+1/n)**n
b_n = lambda n: (1-1/n)**(-n)

plt.errorbar(x = pts, xerr = None, y = a_n(pts), yerr = None, fmt = "bx", markersize = "5", markeredgewidth = "2", label = "$a_n$")
plt.errorbar(x = pts, xerr = None, y = b_n(pts), yerr = None, fmt = "rx", markersize = "5", markeredgewidth = "2", label = "$b_n$")
plt.plot(pts, [np.exp(1)]*len(pts), color = "black", linewidth = 2, label = "$e$")
plt.xlim(1.5, 14.5)
plt.ylim(2.0, 3.5)
plt.legend(loc = "best")
plt.setp(plt.gca().get_legend().get_texts(), fontsize = "22")
plt.show()

So we're going to use the following inequality:

$$\forall n \in \mathbb{N} ~ : ~~~~~ \left ( 1 + \frac{1}{n} \right ) ^n ~~~~<~~~~ e ~~~~<~~~~ \left ( 1 - \frac{1}{n} \right ) ^{-n} \tag*{$\circledast$} \\ ~ \\$$


Thesis

$$\forall n \in \mathbb{N}, ~ n \geq 2 ~ : ~~~~~ e \cdot \left ( \frac{n}{e} \right )^n ~~~~<~~~~ n! ~~~~<~~~~ n \cdot e \cdot \left ( \frac{n}{e} \right )^n \\ ~ \\$$


Proof By Induction

Base Case

We begin with $n = 2$ and get

$$\begin{align} & ~ && e \cdot \left ( \frac{2}{e} \right )^2 ~~~~&&<~~~~ 2! ~~~~&&<~~~~ 2 \cdot e \cdot \left ( \frac{2}{e} \right )^2 \\ ~ \\ & \Leftrightarrow && e \cdot \frac{4}{e^2} ~~~~&&<~~~~ 1 \cdot 2 ~~~~&&<~~~~ 2 \cdot e \cdot \frac{4}{e^2} \\ ~ \\ & \Leftrightarrow && \frac{4}{e} ~~~~&&<~~~~ 2 ~~~~&&<~~~~ \frac{8}{e} \\ ~ \\ &\Leftrightarrow && 2 ~~~~&&<~~~~ e ~~~~&&<~~~~ 4 ~~~~ \\ \end{align} $$

Which is a true statement.

Inductive Hypothesis

Therefore the statement holds for some $n$. $\tag*{$\text{I.H.}$}$

Inductive Step

$$\begin{align} & ~ && e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \\ ~ \\ & = && (n+1) \cdot \frac{1}{e} \cdot e \cdot \left ( \frac{n+1}{e} \right )^n\\ ~ \\ & = && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot \left ( \frac{n+1}{n} \right )^n\\ ~ \\ & = && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot \left ( 1 + \frac{1}{n} \right )^n\\ ~ \\ & \overset{\circledast}{<} && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot e\\ ~ \\ & \overset{\text{I.H.}}{<} && (n+1) \cdot n!\\ ~ \\ & = && (n+1)!\\ ~ \\ & = && (n+1) \cdot n!\\ ~ \\ & \overset{\text{I.H.}}{<} && (n+1) \cdot n \cdot e \cdot \left ( \frac{n}{e} \right )^n\\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n}{e} \right )^{n+1} \cdot e \\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( \frac{n}{n+1} \right )^{n+1} \cdot e \\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{n+1} \cdot e \\ ~ \\ & \overset{\circledast}{<} && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{-(n+1)} \\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \\ ~ \\ \end{align} $$

Conclusion

Therefore the statement holds $\forall n \in \mathbb{N}, ~ n \geq 2$. $$\tag*{$\square$}$$

$\endgroup$
1
$\begingroup$

In an attempt to prove it by induction, you'll reach a stage where you need to prove $$\left(1+\frac{1}{n}\right)^n < e.$$

Consider the $i^\text{th}$ term in the binomial expansion of $(1+1/n)^n$: $$\frac{n!}{(n-i)! i!} \cdot \frac{1}{n^i} < \frac{1}{i!}.$$ This is easily provable as the $i^\text{th}$ term is $$\frac{n(n-1) \cdots (n-i +1)}{n \cdot n \cdots n} \cdot \frac{1}{i!} < \frac{1}{i!}.$$

So, $$\left(1 + \frac{1}{n}\right)^n < e.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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