5
$\begingroup$

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.

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

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

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

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

$\endgroup$
1
$\begingroup$

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.

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

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.

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

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.