# Proving upper bound on a term involving binomial coefficients [closed]

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?

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.

• 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. Jun 29 at 11:41
• @manifolded You may search it. For example, see (15) in ams.org/journals/proc/2013-141-03/S0002-9939-2012-11387-5/… Jun 29 at 12:03
• @manifolded Also, see L. Gordon, “A stochastic approach to the gamma function”, Amer. Math. Monthly, 9(101), 1994, 858-865. Jun 29 at 12:08

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