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

Question

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

Answer 1

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

Answer 2

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