Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 –  Gold Feb 21 '13 at 6:40
1  
@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
2  
@AD Non asymptotic versions exist. –  Did Feb 21 '13 at 6:59
show 3 more comments

4 Answers

up vote 7 down vote accepted

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

share|improve this answer
1  
Well, this is impressive, +1. –  1015 Feb 21 '13 at 7:06
    
I love central binomial coefficients! –  Byron Schmuland Feb 21 '13 at 7:07
    
Thank you so much –  Gold Feb 21 '13 at 7:08
    
+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. –  Byron Schmuland Feb 21 '13 at 19:28
show 1 more comment

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

share|improve this answer
add comment

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.

share|improve this answer
3  
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
2  
@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
add comment

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.

share|improve this answer
    
after your hint I had done this induction proof. Thank You so much. –  Gold Feb 21 '13 at 8:17
    
I'm happy to help! –  JavaMan Feb 21 '13 at 16:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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