# How can we prove the Inequality : $\frac {n!}{ 2^{n-1}((\frac {n-1}{2})!)^2} \leq \sqrt{n}$

How can we prove the following inequality? For every odd positive integer $n$,

$$\frac {n!}{ 2^{n-1}((\frac {n-1}{2})!)^2} \leq \sqrt{n}$$

Thank You.

• Have you tried applying some form of Stirling's formula, to see what comes out? – Gerry Myerson Feb 21 '13 at 6:34
• is it for $n$ odd (else $\frac{n-1}{2}$ isn't an integer) (i hope odd is the right one) – Dominic Michaelis Feb 21 '13 at 6:36
• Sorry I forgot to mention that $n$ is odd – Kumar Feb 21 '13 at 6:40
• @GerryMyerson Something similar to Stirling would surely help, but we cannot apply Stirling right ahead since that is an asymptotic inequality. – AD. Feb 21 '13 at 6:49
• @AD Non asymptotic versions exist. – Did Feb 21 '13 at 6:59

In my answer here, I show that $${2n\choose n}{1\over 4^n}\leq {1\over\sqrt{\pi n}}.$$

Substitute $(n-1)/2$ for $n$ to get $${n-1\choose (n-1)/2}{1\over 2^{n-1}}\leq {1\over\sqrt{\pi (n-1)/2}}\leq{1\over\sqrt{n}},$$ the final inequality being valid for $n\geq 3$, since $\pi (n-1)/2>n$ for such $n$.

• Well, this is impressive, +1. – Julien Feb 21 '13 at 7:06
• I love central binomial coefficients! – user940 Feb 21 '13 at 7:07
• +1 Nice! :) Perhaps you have some idea of using a binomial expansion and some orthogonality method in order to pick the mid term? – AD. Feb 21 '13 at 7:18
• @AD. Sorry, I don't have any ideas along those lines. – user940 Feb 21 '13 at 19:28
• @ByronSchmuland No problem at all..... – AD. Feb 21 '13 at 19:32

Hint:

For $k\geq0$ we need to show $$a_k=\frac{(2k+1)!}{2^{2k}(k!)^2}\leq\sqrt{2k+1}=b_k$$

Now $$a_{k+1}=\frac{(2k+3)!}{2^{2k+2}((k+1)!)^2}= \frac{(2k+3)(2k+2)}{4(k+1)^2}\cdot \frac{(2k+1)!}{2^{2k}(k!)^2}=\frac{(2k+3)(2k+2)}{4(k+1)^2}\cdot a_k$$ So if we knew $a_k\leq b_k$ for some $k$ then could we perhaps continue with induction...?

A nicer proof might be hidden in the in the binomial formula - something like $$2^{2k} = (1+1)^{2k} =\sum_{j=0}^{2k} \frac{(2k)!}{j! (2k-j)!}$$ where the mid term is of interest...

As Gerry Mentioned, Stirling formula will show it (as this is only an asymptotic behaviour we first needs a lower bound for which we know the equation is true). If you don't want to use such a hammer, you should try it with induction.

• We can not use Stirling for specific $n$ without further investigation, it is an asymptotic inequality. – AD. Feb 21 '13 at 6:50
• @Ad. did you downvote? tell me if you don't like the edit – Dominic Michaelis Feb 21 '13 at 6:57
• @AD Non asymptotic versions exist. – Did Feb 21 '13 at 7:02
• @DominicMichaelis I give you +1 for the second comment (thus proving I did not downvote you).. – AD. Feb 21 '13 at 19:41

For completeness, here is the proof by induction:

Base Case: The case $n = 1$ is easy to check.

Inductive Step: Assume that $$\frac{k!}{2^{k-1} \left( \frac{k-1}{2} \right)!^2} \leq \sqrt{k}.$$ We aim to show that this implies $$\frac{(k+2)!}{2^{k+1} \left( \frac{k+1}{2} \right)!^2} \leq \sqrt{k+2}.$$

We have

\begin{align} \frac{(k+2)!}{2^{k+1} \left( \frac{k+1}{2} \right)!^2} &= \frac{(k+2)(k+1)}{4(\frac{k+1}{2})^2} \cdot \frac{k!}{2^{k-1} \left( \frac{k-1}{2} \right)!^2} \\ &\leq \frac{(k+2)(k+1)}{4(\frac{k+1}{2})^2} \cdot \sqrt{k} \\ &= \frac{k+2}{k+1} \sqrt{k} \\ &\leq \sqrt{k+2} \end{align} which occurs if and only if $\left( \frac{k+2}{k+1}\right)^2 k \leq k+2$. I will leave the last inequality for you to check.

• after your hint I had done this induction proof. Thank You so much. – Kumar Feb 21 '13 at 8:17
• I'm happy to help! – JavaMan Feb 21 '13 at 16:33