Show that if $n>2$, then $(n!)^2>n^n$.

Question

Show that if $n>2$, then $(n!)^2>n^n$.

My work:
I tried to apply induction.
So, at the induction step, I need to prove,
$n^n>(n+1)^{n-1}$
Here, I tried to use induction again without any luck. I also took log of both sides, but I did not get anything. Please help!

Answer 1

Use a multiplicative variant of Gauss's trick: $$ (n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n $$

Answer 2

I think I saw a similar question here, but I can't remember where I saw it.

Here is the way:

$$(n!)^2=[1\times 2\times 3\times...\times n][1\times 2\times 3\times...\times n]$$ By grouping terms in pairs as in Gauss' trick, we write: $$(n!)^2=\prod_{i=1}^{n}i(n+1-i)$$ It's easy to see that $i(n+1-i)\geq n$ for every $i\in\{1,2,...,n\}$. Thus, we have: $$(n!)^2=\prod_{i=1}^{n}i(n+1-i)\geq n^n$$

I'll leave proving that we have a strict inequality for $n\geq 2$ to you

Answer 3

There is also the following combinatorial proof.

Let $S_n$ be a set of permutations of $n$ elements and $T_n$ be a set of sequences of length $a_1, a_2, \ldots, a_n$ with $1 \le a_i \le n$. We will construct a surjective mapping from $S_n \times S_n$ to $T_n$. This will imply that $|S_n \times S_n| \ge |T_n|$ which is what we want. For $n \ge 3$ at least one element will also have more that one pre-image.

Consider a pair of two permutations $(\pi_1, \pi_2) \in S_n \times S_n$. Consider a cycle ($c_1 c_2 \ldots c_k$) of $\pi_1$ where $c_1$ is the smallest element of the cycle (that is $c_1 < c_i$). For each such cycle we set $a_{c_i}$ equal to $c_1$-th elements of $\pi_2$ (which we treat as a sequence). That way we produce a sequence {${a_k}$}.

For example, let $\pi_1 = (1) (2 5) (3 6) (4)$ and $\pi_2 = [3, 1, 2, 4, 5, 6]$. Note that we write $\pi_1$ in cycle notation while we treat $\pi_2$ as a sequence. Then $a = [3, 1, 2, 4, 1, 2]$. Note that $\pi_1$ has $4$ cycles hence $a$ has four sets of equal elements. The value for each set of equal elements is determined by $\pi_2$. Also note that last two elements of $\pi_2$ in our example are "ignored" during the construction of the sequence. That is $\pi_1 = (1) (2 5) (3 6) (4)$ and $\pi_2 = [3, 1, 2, 4, 6, 5]$ also maps to the same sequence.

Now it is quite easy to prove that every sequence $a_1, \ldots, a_n$ has at least one pre-image. The $\pi_1$ permutation consists of cycles of equal elements in $a$ and $\pi_2$ determines values of these sets of equal elements.

Also for $n \ge 3$ the sequence $1, 1, \ldots, 1$ has at least two pre-images: $\pi_1 = (1 2 \ldots n)$ and $\pi_2$ equal to any permutations which starts with $1$.

Answer 4

Divide both sides by $n^{n-1}$ to arrive at $$ n>\left(1+\frac 1n\right)^{n-1}$$ to be shown. You may recognize that the right hand side converges to $e$, so we're in good shape. However, that is not explicit enough. So multiply with $(1-\frac1n)^{n-1}$ to get $$ n\cdot \left(1-\frac1n\right)^{n-1}>\left(1-\frac1{n^2}\right)^{n-1}$$ as goal. The right hand side is $<1$ for $n>1$. On the left hand side make use of Bernoulli's inequality $(1+x)^r\ge 1+rx$ if $x\ge-1$, $r\in\mathbb N_0$. So we have indeed $$ n\cdot \left(1-\frac1n\right)^{n-1}\ge n\cdot\left(1-\frac{n-1}n\right)=1>\left(1-\frac1{n^2}\right)^{n-1}.$$

Answer 5

so let us take step $n=3$

$n!=6$

clearly $6^2>3^3$

now let us try $n+1$

$(n+1)!=n*(n)!$

now we have

$((n+1)*(n!))^2>(n+1)^{n+1}$

now

$(n+1)^2 *(n!)^2>(n+1)^n* (n+1)$

for $n>2$ clearly $(n+1)^2>(n+1)$

and $(n+1)*(n!)^2>(n+1)^n$

Answer 6

From your inequality, one can have $$\left(\frac{n+1}{n}\right)^{n-1}<n. $$ Note that $$\left(\frac{n+1}{n}\right)^{n-1}=\frac{\left(\frac{n+1}{n}\right)^{n}}{\frac{n+1}{n}}<\left(\frac{n+1}{n}\right)^{n}$$ and the sequence $\{\left(\frac{n+1}{n}\right)^{n}\}$ is increasing and bounded by $e$. Hence it is easy to see that your inequality holds.

Answer 7

Note that $$\begin{align}n^n\gt (n+1)^{n-1}&\iff n\cdot n^{n-1}\gt (n+1)^{n-1}\\&\iff n\gt \left(\frac{n+1}{n}\right)^{n-1}\\&\iff n\cdot\left(\frac{n+1}{n}\right)\gt \left(\frac{n+1}{n}\right)^{n}\\&\iff n+1\gt\left(1+\frac 1n\right)^{n}.\end{align}$$ By the way, since $$3\gt \left(1+\frac 1n\right)^{n}\ \ \ \ \ (n\gt1),$$ if $n\gt 2$, then the following holds : $$n+1\gt 3\gt \left(1+\frac 1n\right)^{n}.$$ This means that $n^n\gt (n+1)^{n-1}$ holds for $n\gt 2$.

Answer 8

HINT: We know, $2(n-2)>(n-2)$ , therefore $2(n-1)>n$ Similarly, $3(n-2)>n$ ....... ....... We continue this upto $(n-2)$ terms, and then multiply. What do you get? $(n-1)!^2>n^{n-2}$ Arranging this we can easily get $(n!)^2 > n^n $

Answer 9

Here's how we go about it $$ (n!)^2=\prod\limits_{k=1}^{n}k(n+1-k) $$

Let $$ D=k(n+1-k)-n=(n-k)(k-1) $$

Now, $$ D= \left\{ \begin{array}{ll} 0 & \mbox{if } k=1,n\\ 0 & \mbox{if } n=1,2\\ p & p>0 \mbox{ } \forall \mbox{ } k\in(1,n) \mbox{ and } n\neq1,2 \end{array} \right. $$

Taking various values of $k$ between $1$ and $n$, we get $$ \begin{aligned} 1(n) &= n\\ 2(n-1) &> n \\ & \vdots \\ (n-1)(2) &> n \\ n(1) &= n \end{aligned} $$

Multiplying these, we get $$ (n!)^2 \geq n^n $$ with equality holding when $n=1 \text{ or } 2$