Prove by mathematical induction that $n! < n^n$ where $n > 1$ [duplicate]

$\begingroup$

Basic step

Show that $P(2)$ is true:

$$2! < (2)^2$$

$$1*2 < 2*2$$

$$2 < 4 \quad \text{(which is true)}$$

Inductive Step

Assume $P(k) \implies (k)! < (k)^k $ is true

then, I'm not sure how to continue

$\endgroup$ 2

4 Answers

$\begingroup$

If $k!<k^k$ then $(k+1)!<k^k\cdot(k+1)<(k+1)^k(k+1)=(k+1)^{k+1}$.

$\endgroup$ $\begingroup$

When $n=2$,

$n!=2<n^n=4$

Assume when $n=k$,$k!<k^k$ is true,i.e.$\frac{k^k}{k!}>1$

When$\ n=k+1$

We consider $$\frac{k+1^{k+1}}{(k+1)!}$$$$=\frac{k+1^{k}}{k!}$$$$\frac{k+1^{k}}{k!}>\frac{k^k}{k!}>1$$So, when $n=k+1$,$n!<n^n$ is right.

$\endgroup$ $\begingroup$

You did the base case now assume that $n! < n^n$. Multiply by $n+1$ on both sides$$(n+1)n! < (n+1)n^n$$that is$$(n+1)! < (n+1)n^n$$But $(n+1)n^n < (n+1)(n+1)^n = (n+1)^{n+1}$ so$$(n+1)! < (n+1)^{n+1}$$

$\endgroup$ $\begingroup$

For the inductive step, you need to show that for $n>1$,

$$n!<n^n\implies(n+1)!<(n+1)^{n+1}.$$

This can be rewritten$$n!<n^n\implies n!<(n+1)^{n},$$ which is obvious as $n^n<(n+1)^n$.

$\endgroup$