Inductive Proof of $n! < n^n$

Question

Looking at the Wikipedia page on Mathematical Induction, I see that $n! < \frac{n^n}{2^n}\; \forall n>6$
I have been trying to prove that $n! < n^n \; \forall n>5$ using induction myself and my result is a clear special case of the above inequality. Does anyone have any hints on how to show either of these using induction? This came up when a student inquired about proving the convergence of a series, and induction seemed easier to show than a proof using Stirling's Approximation, but I can't seem to find a proof.

Answer 1

Actually, $n!<n^n$ for $n>1$. The case $n=2$ is proved by inspection.

Suppose $n!<n^n$, for $n\ge2$; then $(n+1)!=(n+1)n!<(n+1)n^n$.

Moreover, from $n<n+1$, we deduce $n^n<(n+1)^n$. So we're done.

---

For $n!<n^n/2^n$, it's true only for $n>5$: indeed $6!=720$, while $6^6/2^6=729$.

So assume $n!<n^n/2^n$, for $n\ge6$. Then $$ (n+1)!=(n+1)n!<(n+1)\frac{n^n}{2^n} $$ and so we need to prove that $$ (n+1)\frac{n^n}{2^n}\le\frac{(n+1)^{n+1}}{2^{n+1}} $$ which is equivalent to $$ 2n^n\le (n+1)^n=n^n+\binom{n}{1}n^{n-1}+\sum_{k=2}^n\binom{n}{k}n^{n-k} $$ and this is clearly true.

Answer 2

Hint: Show $(n+1)n^n < (n+1)^{n+1}$.

Answer 3

Fill in the details:

$$(n+1)!=(n+1)n!<(n+1)n^n<(n+1)(n+1)^n=(n+1)^{n+1}$$

Answer 4

$$\underbrace{n!=1*2*3\; ...*\;n}_{n\text{ digits}}$$

$$\underbrace{n^n=n*n*n\;...*\;n}_{n\text{ digits}}$$

Start with the first digit in each and proceed until reaching $n$.

$$1<n$$ $$2<n$$ $$3<n$$ $$\vdots$$ $$n=n$$

This should make it obvious that $n!<n^n$.

Answer 5

$(1+1+...+1)^{n}$ use multinomial expansion formula Then $(1+1+...+1)^{n}>{n\choose{1}{1}{...}{1}}$