Recursive proof that $n^n \geq n!$

Question

So I'm trying to prove, by induction, that $$ n^n \geq n!, \forall n\geq1$$

Base case:

$$ \text{For } n=1, 1^1 = 1 \geq 1 = 1!$$

Hypothesis:

$$ n^n \geq n!$$

Step:

$$ \text{Trying to prove: } n^{n+1} \geq (n+1)! $$

Now, somewhere around here I get some contradicting things. For example, if I start from the right side I get:

$$ (n+1)! = (n+1)\cdot n! \leq (n+1)\cdot n^n = n\cdot n^n + n^n = n^{n+1} + n^n$$

Based on this I would need $n^{n+1} + n^n$ to be less than or equal to $n^{n+1}$, which is certainly not true. Something similar happens when I go the other way.

Any ideas what I'm doing wrong here? Thanks.

Answer 1

$(n+1)! = (n+1)\cdot n! \leq (n+1)\cdot n^n$ by induction hypothesis, and $(n+1)\cdot n^n\leq (n+1)\cdot (n+1)^n = (n+1)^{n+1}$. Done.

Answer 2

You are trying to prove :

$$(n+1)^{n+1} \geq (n+1)!$$

Not :

$$n^{n+1} \geq (n+1)!$$

Answer 3

You need to show that $(n+1)^{n+1} \geq (n+1)!$, not that $n^{n+1} \geq (n+1)!$.

Here are some similar questions asked before: you can check your work against any of them if you'd like.

• Induction Proof $n! < n^n$
• Show that $n!<n^n $ where $n>1$ and is a Positive Integer
• Proof of $\forall n \in \Bbb N$, $n > 2 \implies n! < n^n$

For future reference, Approach0 is an excellent resource to search for similar questions (much better than the SE functionality itself). All the best.

Answer 4

You should try to prove that $$(n+1)^{n+1} \ge (n+1)!$$

\begin{align} (n+1)^{n+1} &= (n+1) (n+1)^n\\ &\ge(n+1)n^n \end{align}

Now use induction hypothesis.

Answer 5

As an alternative: $$ n! = \underbrace{{n(n-1)(n-2)\cdots 3\cdot 2\cdot 1}}_{n\ \text{times}} \\ n^n = \underbrace{n \cdot n\cdot n \dots n}_{n\ \text{times}} $$

Note that: $$ {n! \over n^n} = \frac{n(n-1)(n-2)\cdots 3\cdot 2\cdot 1}{n \cdot n\cdot n \dots n} = \\ = \frac{n}{n} \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{2}{n} \cdot \frac{1}{n} $$

Now note that for any $n \ge 2$: $$ \frac{n!}{n^n} < 1 $$