5
$\begingroup$

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.

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

3 Answers 3

9
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.