Growth of ratio of binomials polynomial or exponential?

108 Views Asked by At

Is the growth of

$$ \dfrac{\binom{2n}{\sqrt{n}}}{\binom{n}{\sqrt{n}}} $$

polynomial or exponential (or other kind of growth) in $n$?

I tried using the Stirling's approximation, which gives (ignoring the constants):

$$2^{2n}n^n\cdot\dfrac{\sqrt{n-\sqrt{n}}\cdot(n-\sqrt{n})^{n-\sqrt{n}}}{\sqrt{2n-\sqrt{n}}\cdot(2n-\sqrt{n})^{2n-\sqrt{n}}}$$

but how to estimate the growth of this?

1

There are 1 best solutions below

2
On BEST ANSWER

Without Stirling: $$ R_n=\frac{\binom{2n}{\sqrt{n}}}{\binom{n}{\sqrt{n}}}=\prod_{k=0}^{\sqrt{n}}\frac{2n-k}{n-k}. $$ For every $k\leqslant\sqrt{n}$, $$2\leqslant\frac{2n-k}{n-k}\leqslant\frac{2n}{n-\sqrt{n}},$$ hence $$2^{\sqrt{n}}\leqslant R_n\leqslant2^{\sqrt{n}}\left(1-1/\sqrt{n}\right)^{-\sqrt{n}}.$$ The last factor on the RHS converges to $\mathrm e$ hence this is enough to show that $$R_n=\Theta\left(2^{\sqrt{n}}\right).$$ More generally, if $x_n=O(\sqrt{n})$, then $$\frac{\binom{2n}{x_n}}{\binom{n}{x_n}}=\Theta\left(2^{x_n}\right).$$