Proving by induction that $\frac{1}{n} \ge \frac{n!}{n^n}$

Question

I have been trying to prove by induction that for all $n \ge 0, \frac{1}{n} \ge \frac{n!}{n^n} $

Here is my proof so far:

Prove that for $ n = 1, \frac{1}{n} \ge \frac{n!}{n^n} $

$ \frac{1}{1} = 1 $

$ \frac{1!}{1^1} = 1 \le 1 $

Next, assume there exists $ n \ge 0 $ such that $ \frac{n!}{n^n} \le \frac{1}{n}. $. We'll prove that $ \frac{1}{n+1} \ge $ $\frac{(n+1)!}{(n+1)^{n+1}} $.

$\frac{(n+1)!}{(n+1)^{n+1}} = \frac{(n!)(n+1)}{(n+1)^{n+1}} = \frac{n!}{(n+1)^n} \lt \frac{n!}{n^n} \le \frac{1}{n}$

However, I don't know how to show now that $\frac{n!}{(n+1)^n} \le \frac{1}{n +1}$

Answer 1

Looks like a trivial proof holds. $n!$ has $n$ terms, each $\le n$. So $\frac{n!}{n^n}=\frac{1}{n}\times C\le \frac{1}{n}$, since $C=\frac{2}{n}\times...\frac{n}{n}\le 1$.

Answer 2

Just note that $$\frac{1}{n}\ge \frac{n!}{n^n} \iff n^n\ge n! \cdot n$$ $$\iff n^{n-1}\ge n!$$

Now assume that for some $n\ge 1$ the above proposition holds $$(n+1)^n\ge (n+1)!$$ $$\iff (n+1)^{n-1}\ge n!$$

But this is trivial since $(n+1)^{n-1}\ge n^{n-1}\ge n!$

Answer 3

If you must have an induction proof, prove the more general inequality:

For $n\geq m\geq 1,$ $$\frac{m!}{n^m}\leq\frac{1}n.$$

You can prove this by induction on $m.$

When $m=1,$ you have $$\frac{m!}{n^m}=\frac1n\leq\frac1n.$$

Assume true for $m$, and assume $n\geq m+1.$

Then also $n\geq m,$ so by induction: $$\frac{m!}{n^{m}}\leq \frac1n.\tag1$$ Also, since $n\geq m+1,$ $$\frac{m+1}{n}\leq 1.\tag2$$

Multiply $(1)$ and $(2)$ together (which we can do because all values are positive) and you get:

$$\frac{(m+1)!}{n^{m+1}}=\frac{m!}{n^m}\cdot\frac{m+1}{n}\leq \frac1n.$$

---

You can do induction on the original statement, but it takes some finagling. It’s not hard - it amounts to:$$\left(\frac{n+1}n\right)^n\geq\frac{n+1}{n}.$$ But the general theorem here is so direct, and its proof captures the intuitive “non-inductive” proof - that the expression is the product of some number of positive terms, the first $\frac1n,$ and the rest are $\leq1.$