5
$\begingroup$

I am currently working in a problem in Information Theory and I came across a difficult inequality. After many attemps, I simplified the inequality, which now looks at follows.

Consider a positive integer $x \in \{1,2,3,...\}$ and a real number $q \in [1,x]$. Prove that \begin{equation} \sum_{m=1}^{x} \frac{m}{\min(m+q-1,x)} \binom{x}{m} \left( \frac{x-q}{x+q}\right)^m \leq \frac{x-q+2}{x+q} \left[ \left(\frac{2x}{x+q}\right)^x-1 \right] \end{equation}

Note that the LHS and the RHS are equal for $q=1$ and $q=x$. Moreover, please note that

\begin{equation} \sum_{m=1}^{x} \binom{x}{m} \left( \frac{x-q}{x+q}\right)^m =\left[ \left(\frac{2x}{x+q}\right)^x-1 \right]. \end{equation}

At this point, I got stuck. I tried by induction over $x$ first, but I wasn't able to go anywhere as the computations become untractable. I then tried to consider the derivative with respect to $q$, but again I wasn't able to reach any conclusion.

I am used to deal for my research with this kind of inequalities and I usually sort them out by applying in some way Cauchy-Schwarz, Jensen, AM-GM or any power mean inequality or by using some real analysis technique with convex/concave functions. However, in this case, all the classical techniques seem to fail. The main issue seems to be given by the power terms $\left( \frac{x-q}{x+q}\right)^m$, which make the inequality difficult.

If someone can help me by providing new directions/techniques to look at, pointing me out similar inequalities in the literature, or give me new any idea to solve it, I would be grateful.

$\endgroup$
2
  • 1
    $\begingroup$ Can you give details on how this inequality arises? $\endgroup$ Commented Apr 12, 2018 at 21:22
  • $\begingroup$ Dear @IosifPinelis, thanks a lot for your beatiful answer. It is a bit difficult to explain the details here, but I sent you a private email to the email address I found in your website. Many thanks, Enrico. $\endgroup$ Commented Apr 13, 2018 at 12:02

1 Answer 1

6
$\begingroup$

$\newcommand{\al}{\alpha} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}} \newcommand{\EE}{\mathcal E} \newcommand{\F}{\mathcal F} \newcommand{\I}{\mathcal I} \newcommand{\x}{\mathbf x} \newcommand{\size}{\text{size}} \newcommand{\pow}{\text{power}} \newcommand{\st}{\text{stupid}}$

This conjecture is true. Of course, the hardest part of this problem is the presence of the $\min$. So, the crucial point in the proof is the following upper bound:

Lemma 1. \begin{equation*} \frac1{\min(m+q-1,x)}\le\frac Am+\frac Bx, \end{equation*} where \begin{equation*} A:=\frac{(x-q+1)^2}{(x+q-1)^2},\quad B:=1-A=\frac{4 (q-1) x}{(x+q-1)^2}, \tag{3} \end{equation*} \begin{equation*} 1<q\le x,\quad 1\le m\le x. \tag{4} \end{equation*}

In what follows, (3) and (4) will always be assumed. (Recall that the case $q=1$ was already verified by the OP, and it will also follow by continuity.) The proof of Lemma 1 is quite elementary, but a bit tedious, and omitted here.

By Lemma 1, the left-hand side (lhs) of the inequality in question is upper bounded by \begin{equation*} \sum_{m=1}^{x} m\,\Big(\frac Am+\frac Bx\Big) \binom{x}{m} \left( \frac{x-q}{x+q}\right)^m =A (r-1)+\frac{B r (x-q)}{2 x}, \end{equation*} where \begin{equation*} r:=\left(\frac{2x}{x+q}\right)^x. \end{equation*} So, the inequality in question reduces to \begin{equation*} A (r-1)+\frac{B r (x-q)}{2 x}\le \frac{x-q+2}{x+q}\,(r-1), \end{equation*} which can be rewriten as \begin{equation} \de(q):=\de(q,x):=\ln r-\ln\frac{(x+1)^2-1-(q-1)^2}{2 x + 2 q-1}\ge0. \tag{5} \end{equation} It is straightforward but tedious to see that \begin{multline*} [(x+1)^2-1-(q-1)^2]\de'(q) \\ =2 q^3 (x+1)+q^2 \left(2 x^2+x-2\right)-2 q x \left(x^2+x-1\right)-x \left(2 x^3+x^2-4 x+1\right)<0 \end{multline*} for \begin{equation} 1\le q\le x-2/5. \tag{6} \end{equation} So, $\de(q)=\de(q,x)$ is decreasing in $q\in[1,x-2/5]$. Moreover, \begin{multline*} (5 x-1) (20 x-9) ( 120 x-49) \frac d{dx}\de(x-2/5,x) \\ =12000 x^3 \ln (5)-100 x^2 (24+127 \ln (5)) \\ +\left(12000 x^3-12700 x^2+4265 x-441\right) \ln \left(\frac{x}{5 x-1}\right)\\ +5 x (512+853 \ln (5))-541-441 \ln (5). \end{multline*} It is straightforward but tedious to see that the latter expression is positive for all $x\ge1$. (One way to deal with such an expression is to notice that the derivative of a high enough order of an expression of the form $P(x)\ln R(x)$ is a ratio of polynomials if $P(x)$ is a polynomial and $R(x)$ is a ratio of polynomials.) So, $\de(x-2/5,x)$ is increasing in $x\ge1$. Also, $\de(x-2/5,x)|_{x=2}=0.00187\ldots>0$. So, $\de(x-2/5,x)>0$ for $x\ge2$. Recalling that $\de(q)=\de(q,x)$ is decreasing in $q\in[1,x-2/5]$, we see that $\de(q,x)>0$ for $x\ge2$ and $q\in[1,x-2/5]$.

Thus, we get the inequality in question for $x\ge2$ and $q\in[1,x-2/5]$. The case $x=1$ is trivial.

So, it remains to consider the case when $x\ge2$ and $q\in(x-2/5,x]$. This case is much easier than the one considered, because in this case the $\min$ does not cause trouble: indeed, for $q\in(x-2/5,x]$ and $m=2,\dots,x$ we have $\min(m+q-1,x)=x$, a constant. So, in this case the difference between the left- and right-hand sides of the inequality in question times $2 q x (x+q)$ equals $2 x (x^2 - q (x - 2)) - q ((x - q)^2 + 4 x)r$, with $r$ as before. Hence, the inequality in question can be rewritten here as \begin{equation} \de(q):=\de(q,x):=\ln r-\ln\frac{2 x (x^2 - q (x - 2))} {q r ((x - q)^2 + 4 x)}\ge0; \tag{7} \end{equation} here we use the same notation, $\de(q)=\de(q,x)$, for an expression (somewhat similar to but) different from the one in (5). Here, we have \begin{multline*} q (x + q) (x^2 - q (x - 2)) ((x - q)^2 + 4 x)\de'(q) \\ =q^3 (11 - 6 x) x^2 + x^4 (4 + x) + q x^3 (4 - 11 x - 2 x^2) \\ + 2 q^4 (2 - 3 x + x^2) + q^2 x^2 (-20 + 5 x + 6 x^2)<0 \end{multline*} for all $q\in[1,x]$, so that $\de(q,x)$ is decreasing in $q\in[1,x]$. Also, $\de(x,x)=0$ and hence $\de(q,x)>0$ for all $q\in[1,x]$.

Thus, the inequality in question is completely proved.

$\endgroup$
2
  • $\begingroup$ The proof now is quite complete. $\endgroup$ Commented Apr 12, 2018 at 21:22
  • $\begingroup$ Many thanks, your solution is beatiful. $\endgroup$ Commented Apr 13, 2018 at 12:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .