proving that $n^n \le (n!)^2$

Question

I want to prove that $n^n \le (n!)^2$.

Now I tried by induction:

for $n=1$ ,$1=1$ and $P(1)$ is true

I suppose that $P(n)$ is true and I have to demonstrate that $P(n+1)$ is true $$((n+1)!)^2=(n+1)^2*(n!)^2 \le (n+1)^2*n^n=(n+1)(n+1)*n^n=(n+1)^n$$ But I'm not sure about the last passage

Answer 1

Before editing for $n^n \ge (n!)^2$

Note that it is false indeed

$$n^n=\overbrace{n\cdot n \cdot n\cdot...\cdot n} ^{n \, terms} $$

$$(n!)^2=(\overbrace{n\cdot (n-1) \cdot (n-2)\cdot...\cdot 1}^{n \, terms})^2\ge(n\cdot (n-1) \cdot (n-2)\cdot...\cdot 1)\cdot n\ge n^n$$

After editing for $n^n \le (n!)^2$

induction step

$$(n+1)^{n+1}=n^n(n+1)\frac{(n+1)^n}{n^n}=n^n(n+1)\left(1+\frac1n\right)^n\stackrel{Ind. Hyp.}\le(n!)^2(n+1)e \le ((n+1)!)^2$$

which is true for $n\ge 2$.

Answer 2

What you are trying to prove is not true. For large enough $n$ (which means $\ge 3$) it will go the other way. If we just use Stirling's approximation $$(n!)^2 \approx \left(\frac {n^n}{e^n}\sqrt{2\pi n}\right)^2=\frac {n^{2n}}{e^{2n}}2\pi n$$ which will clearly be greater than $n^n$ when $n \gt e^2$. We can use one factor of $n^n$ to be greater than $e^{2n}$ and one to be equal to $n^n$

Answer 3

This is false for $n \ge 3$. $27=3^3 < (3!)^2=36$.

Suppose $n^n <(n!)^2$ and $n \ge 3$. Then $\dfrac{(n+1)^{n+1}/((n+1)!^2)}{n^n/(n!)^2} =(n+1)(1+1/n)^n/(n+1)^2 \lt e/(n+1) \lt 1 $.

This shows that $n^n/(n!)^2$ is a decreasing sequence.

Answer 4

Notice: $(n!) = (1*2*...... *n)^2 = (1*2*...... *n)*(1*2*...... *n)=$

$(1*n) * (2*(n-1)) * ....... * (n*1)$.

If we can prove that $k*(n-k+1) \ge n$ we will have

$(1*n) * (2*(n-1)) * ....... * (n*1) \ge n*n*n*....* = n^n$, and that will be it.

We can probably prove $k*(n-k+1) \ge n$ by induction but I'd rather note:

$k \le n$ and $k\ge 1$ so $k(n-k + 1) = kn - k^2 + k = n + (k-1)n -k^2 + k \ge n + (k-1)k - k^2 +k = n$.

.....

Intuitively this is also a result of AM-GM. $k$ and $n-k + 1$ average to $\frac {n+1}2$ so if $m = \frac {n+1}2$ and $k = m - d$ and $n-k+1 = m + d$ we have $k(n-k + 1) = (m - d)(m+d) = m^2 - d^2 \ge m^2 = \frac {(n+1)^2}4$. If $n\ge 3$ then $\frac {(n+1)^2}4 \ge \frac {(n+1)^2}{n+1} = n+ 1> n$. And for $n=1,2,3$ then $\frac {(n+1)^2}4 = 1, \frac 94, 4 \ge n$.