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

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.

• How do you define $(\sqrt{n})!$? Feb 11, 2022 at 16:06

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

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

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