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

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!

• Calculus can be used to show that the derivative of $x^{m - x}$ is negative for $x\in [m/2, m/2 + 1]$. That would work, but it's probably not the solution you're looking for. – Arthur Jan 16 '14 at 15:55
• Try grouping factors on the left into $n$ groups of $2$ factors such that the product of the two is always at least $n$. – Marc van Leeuwen Jan 16 '14 at 15:56
• @Arthur I don't want to use calculus here. – Hawk Jan 16 '14 at 15:57
• @MarcvanLeeuwen Can you please elaborate what you are saying...I could not understand. – Hawk Jan 16 '14 at 15:58
• @Hawk See the answer by lhf (the one you accepted) for what I meant. – Marc van Leeuwen Jan 16 '14 at 16:52

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$$

• I will just add that since each of the brackets can be estimated from above by $\frac{n+1}2$, we can also get the inequality $n! \left(\frac{n+1}{2}\right)^n$ from this. See also: math.stackexchange.com/questions/992056/… – Martin Sleziak Aug 30 '16 at 9:38

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

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}.$$

• I understood upto convergence to $e$ but could not understand after that. Please elaborate. – Hawk Jan 16 '14 at 16:03

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$

• (n+1)!= (n+1)*n! . You have made a mistake there. – Stranger Forever May 4 at 4:52

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$.

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.

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$.

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$$