Good upper bound on ratio of binomial coefficients

Question

What is the asymptotic behavior of $n/2+k/2 \choose k$/$n\choose k$ for $k\le n/2$. Can we show that it goes down (sub)exponential in $k$ i.e. $n/2+k/2 \choose k$/$n\choose k$ $\le c^{-k^{\epsilon}}$ for some fixed constant $c>1$ and $\epsilon>0$? For $k\le n/2$, we can upperbound $n/2+k/2 \choose k$/$n\choose k$ by $\frac{3n/4 \choose k}{n \choose k}$, can we get a (sub)exponential in $-k$ upper bound on $\frac{3n/4 \choose k}{n \choose k}$? Thanks.

Answer 1

$$\frac{{n/2+k/2 \choose k}}{{n \choose k}} =\prod_{j=0}^{k-1} \frac{L-j}{n-j} \tag1$$

where $L=n/2+k/2 < n$

Now, the factors inside the product are decreasing. Hence we get the upper bound $ (L/n)^k=c^{-k}$ with $c=2n/(n+k)=\frac{2}{1+t}$ where $t=k/n$

For the record, the (first order) Stirling approxmation gives

$$\frac{{n/2+k/2 \choose k}}{{n \choose k}} \approx (1-t^2)^{n/2} \left( \frac{1+t}{4(1-t)} \right)^{k/2} $$

Edited: I tighter bound can be found be bouding each term in $(1)$. I get

$$\frac{{n/2+k/2 \choose k}}{{n \choose k}} \le d^{-k}$$

with $$d = \frac{2 }{1+t} \exp\left( \frac{(t-1/n)(1-t)}{2 (1+t)} \right) \approx \frac{2 }{1+t} \exp\left( \frac{t(1-t)}{2 (1+t)}\right) $$

Answer 2

Using the gamma function$$A=\frac{\binom{\frac{k+n}{2}}{k}}{\binom{n}{k}}=2^{n-k}\frac{ \Gamma \left(\frac{n-k+1}{2} \right) \Gamma \left(\frac{n+k+2}{2} \right)}{\sqrt{\pi } \,\Gamma (n+1)}$$ Assuming $n\gg k$, take logarithms and use Stirling approximation to obtain $$\log(A)=-k \log(2)+\frac{k (k+1)}{2 n}\Bigg[ 1-\frac{1}{2 n}+\frac{k (k+1)}{6 n^2}-\frac{k^2+k-1}{4 n^3}+O\left(\frac{1}{n^4}\right)\Bigg]$$ which gives good bounds since alternating.

Using $n=25$ and $k=10$, this truncated series gives $$\log(A) \sim \frac{2078153}{937500}-10 \log (2)=-4.71478$$ to be compared to the exact value $$\log(A)=-\log \left(\frac{2097152}{18879}\right)=-4.71029$$ which, for $A$, corresponds to a relative error of $0.45$%.

Answer 3

Following @leonbloy, you can get an explicit bound in terms of $k$ as follows. Note that $\frac{L-j}{n-j}=1-\frac{n-L}{n-j}$. Then, using the estimate $1-x\le e^{-x}$ which holds for all positive $x$ we get an estimate of the form $$ e^{-\sum_{j=0}^{k-1} \frac{n-L}{n-j}}. $$ A very rough bound that you can use here now is just noting that $\frac{n-L}{n-j}\ge \frac{n-L}{n} = \frac{n/2-k/2}{n}= \frac{1}{2}-\frac{k}{2n}\ge \frac{1}{4}$ where in the last inequality we have used that $n\ge 2k$. Hence, we have the following bound $$ \frac{\binom{n/2+k/2}{k}}{\binom{n}{k}}\le e^{-\sum_{j=0}^{k-1} \frac{1}{4}}=e^{-k/4}. $$