Asymptotic of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$

Question

I'm trying to figure out the asymptotic estimate of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$. I think it is $\omega(2^{\sqrt{n}})$ and am trying to prove it by showing $\lim_{n \rightarrow \infty} \frac{\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}}{2^{\sqrt{n}}} = \infty$ as wolfram says it should. But can't seem to get it. This is what I've tried so far:

$\frac{1}{2^{\sqrt{n}}}\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!} = \frac{1}{2^n}\frac{[\prod_{i=1}^{n-1} (\sqrt{n}+i)](\sqrt{n})!}{(\sqrt{n})!(n-1)!} \\ = \frac{1}{2^n} \frac{\prod_{i=1}^{n-1} (\sqrt{n}+i)}{(n-1)!}$

But I'm not sure where to go from here.

Answer 1

Summary

As zkutch points out, $\sqrt n!$ is not a well-defined notation since $\sqrt n$ is not an integer when $n$ is not a square.

Here are four approaches to interpret the question. We will not only confirm "it" is indeed $\omega(2^\sqrt n)$, but also give tighter or even optimal estimate as well.

Use $\lfloor x\rfloor!$ instead of x!

The question is about $\displaystyle\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!}$.

Let $k=\lfloor\sqrt n\rfloor$. We have, $$\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!} =\frac{\prod_{i=1}^{k}(i+n-1)}{\prod_{i=1}^{k}i} \ge \frac n1\prod_{i=2}^{k}\frac{n}{i} \ge(\sqrt n)^2\prod_{i=2}^{k}\sqrt n \ge\sqrt n^{\sqrt n}$$

Use $\lceil x\rceil!$ instead of x!

As an easy exercise for readers, show that $$\frac{\lceil\sqrt{n}+n-1\rceil!}{\lceil\sqrt{n}\rceil!(n-1)!} \ge\sqrt n^{\sqrt n}$$

Let $n$ be a square

This is Steven's approach. Let $n = k^2$ for some integer $k$. So, $k = \sqrt n = \lfloor \sqrt n\rfloor$. In the same way as the first approach above, we have,

$$\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}=\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!}\ge\sqrt n^{\sqrt n}.$$

Let us compute a tighter estimate, applying Stirling's formula, $$m!\sim \sqrt{2\pi m}\left(\frac{m}{e}\right)^m,$$ where $\sim$ means the ratio of the two sides converges to 1 when $m$ goes to $+\infty$.

$$\begin{aligned} \frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}&= \frac{(k+k^2-1)!}{k! \cdot (k^2-1)!}\sim \frac{(k+k^2)!}{k! \cdot (k^2)!} \\ &\sim \frac{\sqrt{2\pi (k+k^2)}\left(\frac{k+k^2}{e}\right)^{k+k^2}}{ \sqrt{2\pi k}\left(\frac ke\right)^k \sqrt{2\pi k^2} \left(\frac{k^2}e\right)^{k^2}} \\ &\sim\frac1{ \sqrt{2\pi k} } \left(\frac{k+k^2}k\right)^{k}\left(\frac{k+k^2}{k^2}\right)^{k^2} \\ &= \frac1{ \sqrt{2\pi}}\left(\frac{1+k}{k}\right)^{k^2+k} k^{k-\frac12} \end{aligned}$$

The inequality $\left(\frac{1+k}k\right)^{k+1}\gt e$ tells us that $\left(\frac{1+k}{k}\right)^{k^2+k} \gt e^k.$ So we have $$\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}=\Omega(e^\sqrt n\sqrt n^{\sqrt n-\frac12}).$$

If instead we use the following stronger fact, which can be proved by either l'hospital's rule or Taylor's series for $\ln(1+t)$, $$\left(\frac{1+k}{k}\right)^{k^2+k}\sim e^{k+\frac12},$$ we obtain, $$\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}\sim\frac1{\sqrt{2\pi}} e^{\sqrt n+\frac12}{\sqrt n}^{\sqrt n-\frac12}.$$

Use $\Gamma(x+1)$ instead of $x!$

The natural extension of factorial to non-integers is $\Gamma$ function. The question is about $$\frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)\Gamma(n)}.$$ Since $\ln(\Gamma(x))$ is convex and increasing for $x\ge2$, we have $$\frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)}\ge \frac{\Gamma(\lfloor\sqrt{n}+n\rfloor)}{\Gamma(\lfloor\sqrt{n}+1\rfloor)}$$ So, $$ \frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)\Gamma(n)} \ge\frac{\Gamma(\lfloor\sqrt{n}+n\rfloor)}{\Gamma(\lfloor\sqrt{n}+1\rfloor)\Gamma(n)} =\displaystyle\frac{\lfloor\sqrt{n}+n-1\rfloor!}{\lfloor\sqrt{n}\rfloor!(n-1)!}\ge \sqrt n^\sqrt n.$$

Since we also have Stirling's formula for $\Gamma$ function, $$\Gamma(x+1)\sim \sqrt{2\pi x}\left(\frac{x}{e}\right)^x,$$ we can proceed in the same way as in the approach above but without requiring $k=\sqrt n$ be an integer. In particular, we can obtain $$\frac{\Gamma(\sqrt{n}+n)}{\Gamma(\sqrt{n}+1)\Gamma(n)}\sim \frac1{\sqrt{2\pi}} e^{\sqrt n + \frac12}{\sqrt n}^{\sqrt n -\frac12}.$$

Answer 2

Letting $n=k^2$, considering only sufficiently large integer values of $k$, and using Stirling's approximation: $$ \lim_{k \to \infty} \frac{(k+k^2-1)!}{k! \cdot (k^2-1)!} \ge \lim_{k \to \infty} \frac{(k+k^2)!}{2k^2 \cdot k! \cdot k^2!} \ge \lim_{k \to \infty} \frac{((k+k^2)/e)^{k+k^2}}{2k^2 \cdot \sqrt{2\pi k} \cdot (k/e)^k \cdot \sqrt{2\pi k^2} \cdot (k^2/e)^{k^2}} \\ = \lim_{k \to \infty} \frac{(k+k^2)^{k+k^2} }{ 4\pi k^{3.5} \cdot k^k \cdot k^{2k^2}} \ge \lim_{k \to \infty} \frac{k^{2k} k^{2k^2} }{ 4\pi k^{3.5} \cdot k^k \cdot k^{2k^2}} = \lim_{k \to \infty} \frac{k^{k} }{ 4\pi k^{3.5}} = +\infty. $$

Answer 3

I’m assuming $\sqrt n$ stands for $\lfloor\sqrt n\rfloor$. Using Stirling approximation,

$$\frac{(\sqrt n+n-1)!}{\sqrt n!\,(n-1)!}=\frac1{\sqrt n!}\prod_{i=0}^{\sqrt n-1}(n+i)\ge\frac{n^{\sqrt n}}{\sqrt n!}\ge\left(\frac{ne}{\sqrt n}\right)^{\sqrt n}\frac1{\mathrm{poly}(n)}>\sqrt n^{\sqrt n}$$ for large enough $n$.