Show that $\frac{\left(2n\right)!}{2^{n}n!} \ge \frac{\left(2n\right)!}{\left(n+1\right)^{n}}$.

Question

I am attempting to solve this by induction, yet I am stuck on the last part. Below is my attempted solution.

Show that $\frac{\left(2n\right)!}{2^{n}n!} \ge \frac{\left(2n\right)!}{\left(n+1\right)^{n}}, \forall n \in \mathbf{N} $.

My attempted solution, by induction:

For $n=1$ we have,

$\frac{\left(2\right)!}{2^{1} \cdot 1!} \ge \frac{\left(2\right)!}{\left(1+1\right)^{1}} $

$2 \ge 1$.

Thus, the inequality holds for $n=1$.

Now assume that it holds $\forall k \in \mathbf{N}$.

Then, for $k+1$,

$\left(k+1\right) \frac{\left(2k\right)!}{2^{k}k!} \ge \frac{\left(2k\right)!}{\left(k+1\right)^{k}} \left(k+1\right) $.

This is where I am stuck.

Answer 1

You want to prove $2^n n!\le (n+1)^n$. Use Strling formula or induction on $n$. Here is a proof using induction. When you pass from $n$ to $n+1$ the LHS gets multiplied by $ 2(n+1)$. If you multiply the RHS by this you get $2(n+1)^{n+1}$. This is smaller than $(n+2)^{n+1}$ for all $n>c$ for some relatively small $c$ (I think $c=1$ works already). Indeed dividing both sides by $(n+1)^{n+1}$ you get $(1+1/(n+1))^{n+1}\approx e>2$. Moreover it is bigger than $2$ for $n=1$ already and increases as $n$ gets bigger.

Answer 2

Here’s a way to prove the result directly, without any need for induction, Stirling’s formula, or logs.

The desired inequality is clearly equivalent to $2^nn!\le(n+1)^n$. $2^nn!=\prod_{k=1}^n2k$ is the product of the first $n$ positive even integers; call it $p_n$. The arithmetic mean of these even integers is

$$\frac1n\sum_{k=1}^n2k=\frac2n\sum_{k=1}^nk=\frac2n\cdot\frac{n(n+1)}2=n+1\,.$$

• If $n=2m+1$ is odd, the $n$ even integers are $n+1$ and $n+1\pm 2k$ for $k=1,\ldots,m$.
• If $n=2m$ is even, the $n$ even integers are $n+1\pm(2k-1)$ for $k=1,\ldots,m$.

In the first case

$$\begin{align*} 2^nn!&=(n+1)\prod_{k=1}^m(n+1+2k)(n+1-2k)\\ &=(n+1)\prod_{k=1}^m\left((n+1)^2-(2k)^2\right)\\ &\le (n+1)^{2m+1}\\ &=(n+1)^n\,, \end{align*}$$

and in the second case

$$\begin{align*} 2^nn!&=\prod_{k=1}^m\big(n+1+(2k-1)\big)\big(n+1-(2k-1)\big)\\ &=\prod_{k=1}^m\left((n+1)^2-(2k-1)^2\right)\\ &\le (n+1)^{2m}\\ &=(n+1)^n\,. \end{align*}$$

Answer 3

By the AM-GM inequality you have

$$\sqrt{1 \cdot n} \leq \frac{n+1}{2} \\ \sqrt{2 \cdot (n-1)} \leq\frac{n+1}{2} \\ ...\\ \sqrt{n \cdot 1} \leq \frac{n+1}{2} $$

Multiplying everything together you get $$n! \leq \left( \frac{n+1}{2}\right)^n$$

Answer 4

The numerators are the same, so you can divide through them. For the denominators, note that $\log$ is a monotone increasing function, so if $\log a > \log b$, then $a>b$. If you log LHS denominator then you get $$ \log n! + n \log 2 \approx n \log n +n (1+\log 2) -1 $$ RHS is on the other hand $$ n \log (n+1) = n \log n + 1 + o(1) $$ So LHS denominator grows by a factor of $n$ faster

Answer 5

Here's a way to continue the induction process without resorting to Stirling's formula.
If you assume the statement to be true for $n=k$, you already have
$\dfrac{\left(2k\right)!}{2^{k}k!} \ge \dfrac{\left(2k\right)!}{\left(k+1\right)^{k}}$ (Induction hypothesis)

and for $n=k+1$, the statement should be $$\dfrac{(2(k+1))!}{2^{k+1}(k+1)!} \ge \dfrac{(2(k+1))!}{(k+1+1)^{k+1}} \iff (k+2)^{k+1}\ge 2^{k+1}(k+1)! $$ so proving the statement for $n=k+1$ is same as proving the inequality on the right hand side above. We will call it's right and left hand sides $R,L$ respectively so that what we have to prove can be phrased as $L\ge R$.
Now, from the induction hypothesis, $$\begin{aligned} (k+1)^k \ge 2^kk! &\iff 2(k+1)(k+1)^k \ge 2^{k+1}(k+1)k!=2^{k+1}(k+1)! \\ &\iff 2(k+1)^{k+1} \ge R \qquad \qquad (1)\end{aligned}$$ So, all we have to do is to prove $L\ge R$ is that $L \ge 2(k+1)^{k+1} \qquad (2)$
so that we can combine $(1),(2)$ to get $L\ge R$.
Now $$\begin{aligned} L=(k+2)^{k+1} \ge 2(k+1)^{k+1} & \iff (k+2) \ge 2^{\frac1{k+1}} (k+1) \\ &\iff \dfrac{k+2}{k+1} \ge (1+1)^{\frac1{k+1}} \\ &\iff 1+\dfrac1{k+1} \ge (1+1)^{\frac1{k+1}} \end{aligned}$$ where the last inequality is true by taking $x=1,r=\dfrac{1}{k+1}$ in the generalization to Bernoulli's inequality and $(2)$ follows, since all the implications in the all chains of argument work both ways (i.e they are if and only if statements), you can work from the last step to the first.