Show the following holds for $c\leq 1$: $e^{ck^2/n} \frac{(n!)^2}{(n+k)!(n-k)!} \leq M, \quad \text{for } k = 1, \dots, n.$ for some constant $M$

Question

Show that the following inequality holds for $c\leq1$: \begin{equation} \tag{1} e^{ck^2/n} \frac{(n!)^2}{(n+k)!(n-k)!} \leq M, \quad \text{for $k = 1, \dots, n$} \end{equation} for some constant $M$.

Interestingly, R result shows that when $c>1$, $e^{ck^2/n} \frac{(n!)^2}{(n+k)!(n-k)!}\to \infty$ as $n\to\infty$ for $k=1,\dots,n$. I am wondering if this can be proven.

Hint A: According to the concise and ingenious answer by @Qiaochu Yuan, ($1$) holds for $c\leq \frac12$, and $M$ can be chosen as $1$.

Hint B: $\frac{(n!)^2}{(n+k)!(n-k)!}$ is just $\binom{2n}{n-k}/\binom{2n}{n}$. It might be related to asymptotic behavior for the binomial coefficient. I find the following truths.

1. $\binom{2n}{n} \sim \frac{2^{2n}}{\sqrt{n\pi}}$ for $n$ sufficiently large.
2. $\binom{n}{k} \sim \binom{n}{n/2}e^{-d^2/(2n)} \sim \frac{2^n}{\sqrt{\frac12 n\pi}} e^{-d^2/(2n)}$ if $|\frac{n}{2}-k|=o(n^{2/3})$.
3. $\binom{n}{k}\sim (\frac{ne}{k})^k \cdot (2\pi k)^{-1/2} \cdot \exp\left(-\frac{k^2}{2n}(1+o(1))\right)$ if $n$ is large and $k$ is $o(n)$.

see Wikipedia page for binomial coefficient, and p57-60,66 for the book below.

Spencer, Joel; Florescu, Laura, Asymptopia, Student Mathematical Library 71. Providence, RI: American Mathematical Society (AMS).

ps: In my previous version, the right-hand side of ($1$) is $1$, which is incorrect. I have replaced it with a bounded constant. Thanks, @Qiaochu Yuan, @Mostafa Ayaz, and @Anne Bauval for pointing this out!

This is a simple R code just for checking.

n = 1e5
k = 1:n
c = 1.01  #c=.99
a = 2*lfactorial(n)-lfactorial(n+k)-lfactorial(n-k)
b = c*k^2/n
P = exp(a+b)
max(P)

Answer 1

Here is a similar but weaker statement that we can actually prove. We have

$$\begin{eqnarray} \log \frac{n!^2}{(n+k)!(n-k)!} &=& \log \frac{n(n-1)\dots(n-k+1)}{(n+k)(n+k-1) \dots (n+1)} \\ &=& \sum_{i=1}^k \log \frac{n-k+i}{n+i} \\ &=& \sum_{i=1}^k \log \left( 1 - \frac{k}{n+i} \right) \\ &\le& \sum_{i=1}^k - \frac{k}{n+i} \\ &\le& - \frac{k^2}{n+k} \end{eqnarray}.$$

where we used the inequality $\log (1 + x) \le x$ for $x \in (-1, \infty)$ on the fourth line.

Answer 2

The statement for $k=c=1$ is $$e^{1/n}\le1+\frac1n,$$ which is false.

Edit: this was the first correct answer to the original question (see the end of the post above).

Answer 3

This inequality does not hold for every $C=k=1$. To prove this, note that $$ e^{ck^2/n} \frac{(n!)^2}{(n+k)!(n-k)!}|_{C=k=1}=e^\frac{1}{n}\frac{n}{n+1}, $$ which is always $\ge 1$.

Continuing with general $C$ and $k=1$, the inequality must hold only if $$ e^\frac{C}{n}\frac{n}{n+1}\le 1 \implies e^\frac{C}{n}\le 1+\frac{1}{n}. $$ Starting with $n=1$, one finds a necessary condition for $C$ as $C\le \ln 2$.