6
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Arthur Jan 16 '14 at 15:55
  • 2
    $\begingroup$ Try grouping factors on the left into $n$ groups of $2$ factors such that the product of the two is always at least $n$. $\endgroup$ – Marc van Leeuwen Jan 16 '14 at 15:56
  • $\begingroup$ @Arthur I don't want to use calculus here. $\endgroup$ – Hawk Jan 16 '14 at 15:57
  • $\begingroup$ @MarcvanLeeuwen Can you please elaborate what you are saying...I could not understand. $\endgroup$ – Hawk Jan 16 '14 at 15:58
  • $\begingroup$ @Hawk See the answer by lhf (the one you accepted) for what I meant. $\endgroup$ – Marc van Leeuwen Jan 16 '14 at 16:52
18
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Martin Sleziak Aug 30 '16 at 9:38
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Divide both sides by $n^{n-1}$ to arrive at $$ n>\left(1+\frac 1n\right)^{n-1}$$ to be shown. You may regognize 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}.$$

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

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.