Prove $n! \leq n^n$

Question

Prove by least counter example for all positive integers n. $$ n! \leq n^n$$ I keep getting stuck after proving the least element of the set of counterexamples can not equal 1. Any suggestions would be helpful.

Answer 1

Hint: prove using induction. That is, prove the statement for $n = 1$, then assume the statement holds for some $n$ and prove that the statement holds for $n + 1$.

Edit: Specifically, note that for $n = 1$, we have $n^n = 1$ and $n! = 1$, so this is true.

Then we assume that the statement holds for some integer $n \geq 1$ (that is, we assume $n^n \geq n!$, and try to prove the statement $(n + 1)^{n + 1} \geq (n + 1)!$. But this is true, since $(n + 1)! = n!(n + 1) \leq n^n(n + 1) \leq (n + 1)^n(n + 1) = (n + 1)^{n + 1}$.

Answer 2

Note that we have

$$\begin{align} n!&=n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdots3\cdot 2\cdot 1\\\\ &=n\cdot n\left(1-\frac1n\right)\cdot n\left(1-\frac2n\right)\cdot n\left(1-\frac3n\right)\cdots n\frac3n\cdot n\frac2n\cdot n\frac1n\\\\ &=n^n\cdot\left(1-\frac1n\right)\cdot\left(1-\frac2n\right)\cdot\left(1-\frac3n\right)\cdots \frac3n\cdot \frac2n\cdot\frac1n\\\\ &\le n^n \end{align}$$

since each parenthetical term is less than $1$.

Answer 3

It sounds like want to show that $S = \{n \in \mathbb{N} : n! > n^n\}$ cannot have a smallest element.

So let $n$ be the smallest number in $S$, and (by what you say you have shown) $n>1$.

Then we have that both $n! > n^n$ and $(n-1)! \le (n-1)^{n-1}$, and we want to derive a contradiction.

Hint: What is $n!/(n-1)!$ and what can you say about $n^{n-1} / (n-1)^{n-1}$?

Answer 4

$n!$ is the number of permutations of $S=\{1, \dots, n \}$, while $n^n$ is the number of functions from $S$ to itself. Permutations are functions, so clearly $n! \leq n^n$.