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$ 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$ 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$ Apr 12, 2018 at 21:22
  • $\begingroup$ Many thanks, your solution is beatiful. $\endgroup$ Apr 13, 2018 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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