# Solve by induction: $n!>(n/e)^n$

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

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

-
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. – Qiaochu Yuan Aug 20 '11 at 19:46
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. – Joe Aug 20 '11 at 20:31
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. – LostInMath Aug 20 '11 at 23:05
@Qiaochu What about his tone is challenging? And what about the question would make others feel bad for not being able to solve problems? – Quinn Culver Aug 21 '11 at 12:49
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. – Qiaochu Yuan Aug 21 '11 at 12:56

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

$$(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)$$

Can you solve it from here?

-
Very nicely expressed as a route to a solution! – Geoff Robinson Aug 20 '11 at 20:05
Hmm not sure (n/n+1)^n < 1 – Anil Shanbhag Aug 21 '11 at 17:55
@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. – svenkatr Aug 22 '11 at 3:44
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. – Ragib Zaman Aug 22 '11 at 9:26
@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$). – Geoff Robinson Aug 22 '11 at 21:57

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.

-
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$. – Asaf Karagila Aug 21 '11 at 5:49
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$). – Ragib Zaman Aug 21 '11 at 7:26
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. – Geoff Robinson Aug 21 '11 at 9:00
Nice proof -- Didnt think of problem in this direction -- But then again the main idea was to prove by induction – Anil Shanbhag Aug 21 '11 at 18:00

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

-

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}$.

-
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. – Ragib Zaman Aug 21 '11 at 3:09