Wednesday, December 13, 2017

inequality - Elementary central binomial coefficient estimates




  1. How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ?


  2. Does anyone know any better elementary estimates?




Answer



Here are some crude bounds:



$${1\over 2\sqrt{n}}\leq {2n\choose n}{1\over 2^{2n}}\leq{3\over4\sqrt{n+1}},\quad n\geq1.$$






We begin with the product representations
$${2n\choose n}{1\over 2^{2n}}={1\over 2n}\prod_{j=1}^{n-1}\left(1+{1\over 2j}\right)=\prod_{j=1}^n\left(1-{1\over2j}\right),\quad n\geq1.$$




From
$$ \prod_{j=1}^{n-1}\left(1+{1\over 2j}\right)^{\!\!2}=\prod_{j=1}^{n-1}\left(1+{1\over j}+{1\over 4j^2}\right)\geq \prod_{j=1}^{n-1}\left(1+{1\over j}\right)=n,$$
we see that
$$\left({2n\choose n}{1\over 2^{2n}} \right)^{2} = {1\over (2n)^2}\, \prod_{j=1}^{n-1}\left(1+{1\over 2j}\right)^{\!\!2}
\geq {1\over 4n^2}\, n ={1\over 4n},\quad n\geq1.$$
so by taking square roots, ${2n\choose n}{1\over 2^{2n}}\geq \displaystyle{1\over 2\sqrt{n}}.$



On the other hand, $$ \prod_{j=1}^{n}\left(1+{1\over 2j}\right) \left(1-{1\over 2j}\right)
= \prod_{j=1}^{n}\left(1-{1\over 4j^2}\right)\leq {3\over 4},$$

so that (using the lower bound above), we have
$$ {2n\choose n}{1\over 2^{2n}}=\prod_{j=1}^n\left(1-{1\over2j}\right)\leq{3\over4\sqrt{n+1}}.$$



Alternatively, multiplying the different representations we get
$$n\left[{2n\choose n}{1\over 2^{2n}}\right]^2={1\over 2}\prod_{j=1}^{n-1}\left(1-{1\over4j^2}\right) \,\left(1-{1\over 2n}\right).$$
It's not hard to show that the right hand side increases from $1/4$ to $1/\pi$ for $n\geq 1$.






Edit: You can get better bounds if you know Wallis's formula:




$$2n\left[{2n\choose n}{1\over 4^n}\right]^2={1\over 2}{3\over 2}{3\over 4}{5\over 4}\cdots
{2n-1\over 2n-2}{2n-1\over 2n}={1\over 2}\prod_{j=2}^n\left(1+{1\over 4j(j-1)}\right)$$



$$(2n+1)\left[{2n\choose n}{1\over 4^n}\right]^2={1\over 2}{3\over 2}{3\over 4}{5\over 4}\cdots
{2n-1\over 2n-2}{2n-1\over 2n}{2n+1\over 2n}=\prod_{j=1}^n\left(1-{1\over 4j^2}\right)$$



By Wallis's formula, both middle expressions converge to ${2\over \pi}$.
The right hand side of the first equation is increasing, while the right hand
side of the second equation is decreasing. We conclude that




$${1\over\sqrt{\pi(n+1/2)}}\leq {2n\choose n}{1\over 4^n}\leq {1\over\sqrt{\pi n}}.$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...