1
$\begingroup$

I am trying to show:

$$\binom{n}{k}\left(1-\frac{k}{n}\right)^{2n-2k+2} \left(\frac{k-1}{n}\right)^{2k}\leq \frac{1}{n^2}$$ for $k\in \{2,3,\cdots,n-1\}$ for all $n$

I observe that numerically that is true but analytically, I am not able to look at the term on LHS as a term of a binomial expansion or something like that to get an upper bound. Any ideas?

$\endgroup$
0
2
$\begingroup$

Sketch of a proof:

Fact 1: Let $x, y$ be real numbers with $x \ge 6$ and $3 \le y \le x - 2$. Then $$\ln \frac{\Gamma(x + 1)}{\Gamma(y + 1)\Gamma(x - y + 1)} + (2x - 2y + 2)\ln(1 - y/x) + 2y\ln \frac{y - 1}{x} + 2\ln x \le 0.$$ The proof of Fact 1 is given at the end.

By Fact 1, when $n\ge 6$ and $3 \le k \le n - 2$, we have $$\ln \binom{n}{k} + (2n - 2k + 2)\ln(1 - k/n) + 2k\ln \frac{k - 1}{n} + 2\ln n \le 0.$$ Thus, the desired inequality is true.

When $n \ge 6$ and $k = 2, n - 1$, the desired inequality is verified directly.

When $n \le 5$, the desired inequality is verified directly.

We are done.


Proof of Fact 1:

Denote the LHS by $F(x, y)$. We have \begin{align*} \frac{\partial^2 F}{\partial y^2} &= - \psi'(y + 1) - \psi'(x - y + 1)\\ &\qquad + {\frac {2{x}^{2}y - 2x{y}^{2} - 4{x}^{2} + 4xy - 2{y}^{2} + 2x + 2y - 2}{ \left( x - y \right) ^{2} \left( y - 1 \right) ^{2}}}\\[5pt] &\ge - \frac{1}{y + 1} - \frac{1}{(y + 1)^2} - \frac{1}{x - y + 1} - \frac{1}{(x - y + 1)^2}\\[8pt] &\qquad + {\frac {2{x}^{2}y - 2x{y}^{2} - 4{x}^{2} + 4xy - 2{y}^{2} + 2x + 2y - 2}{ \left( x - y \right) ^{2} \left( y - 1 \right) ^{2}}}\\[6pt] &= \frac{G}{(y + 1)^2(x - y + 1)^2(x - y)^2(y - 1)^2}\\ &\ge 0 \end{align*} where $\psi(\cdot)$ is the digamma function defined by $\psi(u) = \frac{\mathrm{d} \ln \Gamma(u)}{\mathrm{d} u} = \frac{\Gamma'(u)}{\Gamma(u)}$, and \begin{align*} G &= {x}^{4}{y}^{3}-3\,{x}^{3}{y}^{4}+3\,{x}^{2}{y}^{5}-x{y}^{6}+2\,{x}^{3} {y}^{3}-6\,{x}^{2}{y}^{4}+6\,x{y}^{5}-2\,{y}^{6}\\ &\qquad -3\,{x}^{4}y+10\,{x}^{ 3}{y}^{2}-11\,{x}^{2}{y}^{3}+2\,x{y}^{4}+2\,{y}^{5}-6\,{x}^{4}+18\,{x} ^{3}y\\ &\qquad -18\,{x}^{2}{y}^{2}+6\,x{y}^{3}-2\,{y}^{4}-11\,{x}^{3}+30\,{x}^{2 }y-23\,x{y}^{2}+4\,{y}^{3}\\ &\qquad -6\,{x}^{2}+12\,xy-2\,{y}^{2}-2\,x+2\,y-2, \end{align*} and we have used $\psi'(u) \le \frac{1}{u} + \frac{1}{u^2}$ for all $u > 0$, and we have used $G \ge 0$.
Hint for the proof of $G \ge 0$: With the substitutions $x = 6 + t, \ y = \frac{1}{1 + s}\cdot 3 + \frac{s}{1 + s}\cdot (x - 2)$ for $t, s \ge 0$, we have $(1 + s)^6G$ is a polynomial in $s, t$ with non-negative coefficients.

Thus, $F(x, y)$ is convex with respect to $y$. Also, $F(x, 3) \le 0$ and $F(x, x-2) \le 0$. Thus, $F(x, y) \le 0$ for all $x \ge 6$ and $3 \le y \le x - 2$.

We are done.

$\endgroup$
3
  • $\begingroup$ Thanks, can we prove that $\psi'(u)\leq \frac{1}{u}+\frac{1}{u^2}$ for all $u>0$? I do see numerically that is true. $\endgroup$
    – manifolded
    Jun 29 at 11:41
  • $\begingroup$ @manifolded You may search it. For example, see (15) in ams.org/journals/proc/2013-141-03/S0002-9939-2012-11387-5/… $\endgroup$
    – River Li
    Jun 29 at 12:03
  • $\begingroup$ @manifolded Also, see L. Gordon, “A stochastic approach to the gamma function”, Amer. Math. Monthly, 9(101), 1994, 858-865. $\endgroup$
    – River Li
    Jun 29 at 12:08
0
$\begingroup$

This is not a proof.

$$a_k=\binom{n}{k}\left(1-\frac{k}{n}\right)^{2n-2k+2} \left(\frac{k-1}{n}\right)^{2k}$$

Expanding as series for large $n$ and keeping the first term only, we have $$a_2=\frac{1}{2 e^4 n^2}+O\left(\frac{1}{n^3}\right)\qquad \qquad a_3=\frac{32}{3 e^6 n^3}+O\left(\frac{1}{n^5}\right)$$ $$a_4=\frac{2187}{8 e^8 n^4}+O\left(\frac{1}{n^5}\right)\qquad \qquad a_5=\frac{131072}{15 e^{10} n^5}+O\left(\frac{1}{n^6}\right)$$ $$a_{n-4}=\frac{131072}{3 e^{10} n^6}+O\left(\frac{1}{n^7}\right)\qquad \qquad a_{n-3}=\frac{2187}{2 e^8 n^5}+O\left(\frac{1}{n^6}\right)$$ $$a_{n-2}=\frac{32}{e^6 n^4}+O\left(\frac{1}{n^5}\right)\qquad \qquad a_{n-1}=\frac{1}{e^4 n^3}+O\left(\frac{1}{n^5}\right)$$

$\endgroup$

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