# Show $\frac{ (n+k)!}{n! \sqrt{n+k}} \le ( f(n) )^k \sqrt{k!}$ for some function $f$

Let $$k$$ and $$n$$ be positive integers.

Can we show the following inequality: \begin{align} \frac{ (n+k)!}{n! \sqrt{n+k}} \le ( f(n) )^k \sqrt{k!}, \end{align} where $$f(n)$$ is some funciton of $$n$$ only. For this assume that $$n$$ is fixed, and the above must hold for all positive integers $$k$$.

• @Clayton I added a correction. – Lisa Mar 19 at 19:46
• Do you have Stirling's Approximation? Do you have any specific thoughts about the inequality? (Hint: Focus on the fact that $n$ is fixed.) – Clayton Mar 19 at 19:53
• @Clayton Yes, I tried Stirling's bounds. However, I can not decouple $n$ and $k$ in the sum $(n+k)$. – Lisa Mar 19 at 20:01

We cannot show the inequality asked about because the left-hand side essentially grows at a rate like $$k!$$ while the right-hand side grows at a rate of $$c^k\sqrt{k!}$$, for some $$c>0$$. To be more precise, we have for sufficiently large $$k$$, that

$$c_n\cdot\frac{k!}{\sqrt{k}}\leq c_n\frac{(n+k)!}{\sqrt{k}}\leq\frac{(n+k)!}{n!\sqrt{n+ k}}.$$ Thus, if we show the left-hand side cannot be bounded above by $$c^k\sqrt{k!}$$, then we'll be done.

At this point, if the proposed inequality were true, we'd have $$c_n\cdot\frac{\sqrt{k!}}{\sqrt{k}}\leq c^k,$$ which follows just from dividing both sides by $$\sqrt{k!}$$. Here, I'm using $$c=f(n)$$; since $$n$$ is fixed, it means $$f(n)$$ is simply a constant.

Taking $$k^{th}$$ roots and applying Stirling's Approximation, we deduce for $$k$$ sufficiently large, that $$\frac{1}{2}\cdot\left(\frac{k}{e}\right)^{1/2}\leq c.$$ Letting $$k\to\infty$$, we see the left-hand side tends to $$\infty$$, while the right-hand side remains fixed at $$c$$. This is clearly a contradiction, so there is no such $$f$$.

Note: This problem relies on $$n$$ being fixed. If you allow $$n$$ to vary, you can prove that such a function does exist, but $$n$$ will necessarily depend on $$k$$.

Let suppose that such a $$f$$ exists, and fix $$n$$. You have then $$\frac{(n+k)!}{n! \sqrt{(n+k)k!}(f(n))^k} \leq 1$$

Now, when $$k$$ tends to $$\infty$$, you have by Stirling formula $$\frac{(n+k)!}{n! \sqrt{(n+k)k!}(f(n))^k} \sim\frac{\sqrt{2\pi(n+k)} \left(\frac{n+k}{e} \right)^{n+k}}{n! \sqrt{(n+k)}\sqrt{\sqrt{2\pi k} \left(\frac{k}{e} \right)^k}(f(n))^k} = L \frac{(n+k)^{n+k}}{e^{k/2} k^{(2k+1)/4}(f(n))^k}$$

where $$L$$ is a constant independant of $$k$$. Now, note that when $$k$$ tends to $$\infty$$, $$(n+k)^{n+k} = k^{n+k} \left( 1 + \frac{n}{k}\right)^{n+k} \sim k^{n+k} e^n$$

You deduce that $$\frac{(n+k)!}{n! \sqrt{(n+k)k!}(f(n))^k} \sim L' \frac{k^{n+k}}{e^{k/2} k^{(2k+1)/4}(f(n))^k} \sim L' \frac{k^{n- \frac{1}{4}}}{ (\sqrt{e}f(n))^k} k^{k/2}$$

and it is easy to see that the limit when $$k$$ tends to $$+\infty$$ is $$+\infty$$ ($$k^k$$ is stronger than all the other terms).

This is impossible because it should always be $$\leq 1$$.

So there does not exist such a function $$f$$.