3
$\begingroup$

Prove that $2^n(n!)^2 \leq (2n)!$

One can also use the following result to prove the above: $2 · 6 · 10 · 14 · · · · · (4n − 2) = \frac{(2n)!}{ n!}$.

The above relation gives, $(2n)!=2^n n! (1.3.5....(2n-1))$, how to go further.

$\endgroup$
2
$\begingroup$

There are multiple ways. One can even use induction to prove it. Here's the easiest way:

$$2^n(n!)^2=(2^n\cdot n!)\cdot n!=(2n)!!\cdot n!\le (2n)!!\cdot (2n-1)!!=(2n)!$$

$$\therefore\quad 2^n(n!)^2\le (2n)!$$

Here, $n!!$ is the double factorial notation.

This is actually because $n!=1\cdot 2\cdot 3\cdots n\le 1\cdot 3\cdot 5\cdots (2n-1)=(2n-1)!!$


$\endgroup$
3
$\begingroup$

You want to prove that $2^n (n!)^2 \le (2n)!$, but this is equivalent to:

$$2^n \le {2n \choose n} = \frac{(2n)!}{n! \cdot n!}$$

Suppose you have $n$ pairs, each consisting of one woman and one man. Right side counts the number of ways to choose $n$ people from that group. Left side counts the number of ways to choose one person from each pair. After noticing that combinatorial interpretation, the inequality becomes obvious.

$\endgroup$
2
$\begingroup$

$2^n(n!)^2\le (2n)!$. Now divide by $n!$ and get:

$$\iff \underbrace{2n(2(n-1))(2(n-2))\cdots(2(n-(n-1)))}_{n\text{ terms}}\le \underbrace{(2n)(2n-1)\cdots(2n-(n-1))}_{n\text{ terms}}$$

This is true because $2(n-k)\le 2n-k\iff k\ge 0$.

$\endgroup$
1
$\begingroup$

As already noted by Leon Aragones, this is the same as proving $$ a_n=2^n \leq \binom{2n}{n}=b_n\tag{1}$$ that clearly holds for $n=1$. Since: $$ \frac{a_{n+1}}{a_n}=2,\qquad \frac{b_{n+1}}{b_n}=\frac{4n+2}{n+1}\geq 2 \tag{2}$$ we have that $(1)$ holds by induction.

$\endgroup$
1
$\begingroup$

It is sufficient to prove $$2^n\le\binom{2n}{n}\tag 1$$ First, note that $$2^n=(1+1)^n=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}\tag 2$$

Second, note that $$\binom{2n}{n}={\binom{n}{0}}^2+{\binom{n}{1}}^2+\cdots+{\binom{n}{n}}^2\tag 3$$ From $(2),(3)$, you'll get $(1)$.

To get $(3)$, compare the coefficient of $x^n$ in the both sides of $$(1+x)^n(x+1)^n=(1+x)^{2n}.$$

$\endgroup$
0
$\begingroup$

Another approach for this kind of problem : the use of Stirling approximation is very interesting $$m!\approx m^m \sqrt{2\pi m}\,e^{-m}$$ so $$\frac{(2n)!}{2^n (n!)^2}\approx \frac{2^n}{\sqrt{\pi } \sqrt{n}}$$ which is already greater than $1$ for $n=1$. Now, you can easily show (using its derivative) that the expression increases with $n$.

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