11
$\begingroup$

Let $n \ge 2$ be a an integer and $x_1,...,x_n$ are positive reals such that $$\sum_{i=1}^nx_i=\frac{1}{2}$$ Prove that $$\sum_{1\le i<j\le n}\frac{x_ix_j}{(1-x_i)(1-x_j)}\le \frac{n(n-1)}{2(2n-1)^2}$$

Here is the source of the problem (in french) here

Edit:

I'll present my best bound yet on $$\sum_{1\le i<j\le 1}\frac{x_ix_j}{(1-x_i)(1-x_j)}=\frac{1}{2}\left(\sum_{k=1}^n\frac{x_k}{1-x_k}\right)^2-\frac{1}{2}\sum_{k=1}^n\frac{x_k^2}{(1-x_k)^2}$$ This formula was derived in @GCab's Answer.

First let $a_k=x_k/(1-x_k)$ so we want to prove $$\left(\sum_{k=1}^na_k\right)^2-\sum_{k=1}^na_k^2\le \frac{n(n-1)}{(2n-1)^2}$$ But since $$\frac{x_k}{1-x_k}<2x_k\implies \sum_{k=1}^na_k<1 \quad (1)$$ Hence $$\left(\sum_{k=1}^na_k\right)^2\le \sum_{k=1}^na_k$$ Meaning $$\left(\sum_{k=1}^na_k\right)^2-\sum_{k=1}^na_k^2\le\sum_{k=1}^na_k(1-a_k)$$

Now consider the following function $$f(x)=\frac{x}{1-x}\left(1-\frac{x}{1-x}\right)$$

$f$ is concave on $(0,1)$ and by the tangent line trick we have $$f(x)\le f'(a)(x-a)+f(a)$$

set $a=1/2n$ to get $$a_k(1-a_k)\le\frac{4n^2\left(2n-3\right)}{\left(2n-1\right)^3}\left(x_k-\frac{1}{2n}\right)+ \frac{2(n-1)}{(2n-1)^2}$$ Now we sum to finish $$\sum_{k=1}^na_k(1-a_k)\le \frac{2n(n-1)}{(2n-1)^2}$$

Maybe by tweaking $(1)$ a little bit we can get rid of this factor of $2$

$\endgroup$
12
  • $\begingroup$ From a math olympiad, I'll post the original problem just wait a minute. $\endgroup$
    – PNT
    May 7 at 20:37
  • $\begingroup$ Is it from an active (on-going) contest? In that case see math.meta.stackexchange.com/q/16774/42969 $\endgroup$
    – Martin R
    May 7 at 20:52
  • $\begingroup$ No, you can read the date in the paper. It says 6 May so it's yesterday $\endgroup$
    – PNT
    May 7 at 20:53
  • 1
    $\begingroup$ @PNT Could you give some more information on the contest? I.e. what knowledge is assumed / What is the level of the contest? Who is it aimed at? This could greatly restrict the possible techniques $\endgroup$
    – Dr. Mathva
    May 8 at 9:24
  • $\begingroup$ It’s aimed for high school students, for knowledge I think it requires just basic inequalities like CS or AM-GM. @Dr.Mathva $\endgroup$
    – PNT
    May 8 at 12:26

3 Answers 3

6
$\begingroup$

Edit. Eventhough I had in mind the version of the ACM I needed, it all messed up when I tried to find a reference. As for the valid version, I will refer to Vasile Cirtoaje's Algebraic Inequalities. Old and new Methods, p. $267$.


We will employ a powerful technique developed by Vasile Cirtoaje back in $2006$ called the Arithmetic Compensation Method (see, for instance, this document).

Let to this end $$F(x_1, \ldots, x_n):=\sum_{1\leqslant i<j\leqslant n}\frac{x_ix_j}{(1-x_i)(1-x_j)}$$ which is clearly symmetric and continuous on $S:=\left\{(x_1, \ldots,x_n)\mid \sum_{i=1}^n x_i=\frac12, \forall i: x_i\geqslant 0\right\}$. We will now refer to the Remark 1.1 from the document linked above, which basically states that

If $$F(x_1,x_2,x_3,\ldots,x_n)>F\left(\frac{x_1+x_2}2, \frac{x_1+x_2}{2}, x_3,\ldots,x_n\right)\label{(i)}\tag{i}$$ implies $F(x_1,x_2,x_3,\ldots,x_n)\leqslant F(0, x_1+x_2, x_3, \ldots, x_n)$, then $$F(x_1,x_2,x_3,\ldots,x_n)\leqslant \underset{1\leqslant k\leqslant n}\max F\left(\frac1{2k}, \ldots, \frac1{2k},0,\ldots ,0\right)$$

Notice that (\ref{(i)}) is equivalent to (where we will denote, for brevity, $y:=\frac{1}2(x_1+x_2)$) \begin{align*} \frac{x_1x_2}{(1-x_1)(1-x_2)}-\frac{y^2}{(1-y)^2}+\left(\frac{x_1}{1-x_1}+\frac{x_2}{1-x_2}-\frac{2y}{1-y}\right)\sum_{i=3}^n \frac{x_i}{1-x_i}>0\\ \iff \frac{y^2-x_1x_2}{(1-x_1)(1-x_2)(1-y)^2}\left[2y-1+2(1-y)\sum_{i=3}^n \frac{x_i}{1-x_i}\right]>0\\ \iff 2y-1+2(1-y)\sum_{i=3}^n \frac{x_i}{1-x_i}>0 \end{align*}

Where the last equivalence follows from $y^2-x_1x_2\geqslant 0$. We will now turn to the second inequality: \begin{align*} F(x_1,x_2,x_3,\ldots,x_n)- F(0, x_1+x_2, x_3, \ldots, x_n)\leqslant0\\ \iff \frac{x_1x_2}{(1-x_1)(1-x_2)}+\left(\frac{x_1}{1-x_1}+\frac{x_2}{1-x_2}-\frac{2y}{1-y}\right)\sum_{i=3}^n \frac{x_i}{1-x_i}\leqslant0\\ \iff \frac{x_1x_2}{(1-x_1)(1-x_2)(1-2y)}\left[1-2y+2(y-1)\sum_{i=3}^n \frac{x_i}{1-x_i}\right]\leqslant 0\\ \end{align*}

Which is easily seen to follow from (\ref{(i)}). Thus, we conclude that \begin{align*} F(x_1,x_2,x_3,\ldots,x_n)&\leqslant \underset{1\leqslant k\leqslant n}\max F\left(\frac1{2k}, \ldots, \frac1{2k},0,\ldots ,0\right)\\ &= \underset{1\leqslant k\leqslant n}\max \binom{k}{2}\frac{1}{(2k-1)^2}\\ &= \underset{1\leqslant k\leqslant n}\max \frac{k(k-1)}{2(2k-1)^2} \end{align*}

But $f: x\mapsto \frac{x(x-1)}{2(2x-1)^2}$ is increasing on $[1,\infty)$, and, hence, the result follows.

Remark. Based on the difficulty of the other contest problems, this solution seems a bit overkill to me, but I have failed in the attempt to find a simpler method, since most well-known inequalities work in the other direction...

$\endgroup$
10
  • $\begingroup$ Nitpicking: As I understand it, the used “AC method” requires the domain $S$ to be compact. $\endgroup$
    – Martin R
    May 8 at 14:45
  • 2
    $\begingroup$ I'm confused... Don't we want to prove $\leq \frac{k(k-1)}{2(2k-1)^2}$? $\endgroup$
    – Diger
    May 13 at 12:21
  • 1
    $\begingroup$ +1, wonderful proof and method. Would you mind I ask you a question regarding the paper ijpam.eu/contents/2012-80-3/6/6.pdf you quoted before? Did the author make a small mistake in Equation (3.6) in that the summand thereof should be $\displaystyle\frac1{(mx_i-x_1x_2y)(mx_i-t^2y)}$? It seems the author misses the factor $mx_i-t^2y$ on the denominator. $\endgroup$
    – Hans
    May 16 at 1:24
  • 1
    $\begingroup$ Just wondering: For the proof of the ACM, the iteration process can in pinciple be infinitely long, or? Starting with $x_1>...>x_n$, we have $y_1=y_2=\frac{x_1+x_2}{2}$ and $x_1>y_1=y_2>y_3>...y_n=x_n$. Repeating the step successively with $y_2$ and $y_3$ will give a nested sequence $z_{1,k},...,z_{n,k}$, where $z_{m,0}=x_m$ and $z_{m,1}=y_m$, with the properties $$x_1>z_{1,k}>...>z_{n,k}>x_n \, .$$ $z_{1,k}$ decreases monotonically, and $z_{n,k}$ increases monotonically in $k$, while both being bounded below/above. Thus we have convergence, but why does it converge to the same number? $\endgroup$
    – Diger
    May 16 at 13:36
  • 1
    $\begingroup$ @Diger: Did you see Lemma 2.1-2.3 in ijpam.eu/contents/2012-80-3/6/6.pdf? $\endgroup$
    – Hans
    May 16 at 20:09
3
+25
$\begingroup$

You should be able to look for the maximum, by the method of Lagrange. We set $$F(x_1,...,x_n) \equiv \sum_{i\neq j} \frac{x_i x_j}{(1-x_i)(1-x_j)} \stackrel{\text{wts.}}{\leq} \frac{n(n-1)}{(2n-1)^2} \, ,$$ and define the Lagrange-function as $$L(x_1,...,x_n) = F(x_1,...,x_n) - \lambda \left(x_1+...+x_n-1/2\right) \,.$$ At an extremum we have $$\nabla L = 0 \qquad , \qquad \nabla=\begin{pmatrix} \partial_{x_1} \\ \vdots \\ \partial_{x_n} \\ \partial_\lambda\end{pmatrix} \, ,$$ in coordinates \begin{align}\frac{2}{(1-x_k)^2} \sum_{\substack{i=1 \\ i\neq k}}^n \frac{x_i}{1-x_i} &= \lambda \quad\text{for}\quad k=1,...,n \tag{1} \\ \sum_{i=1}^n x_i &= 1/2 \tag{2} \, .\end{align} Multiplying Equation (1) by $\frac{(1-x_k)^2}{2}$ and adding $\frac{x_k}{1-x_k}$ to both sides gives $$c=\sum_{i=1}^n \frac{x_i}{1-x_i} = \frac{\lambda}{2} (1-x_k)^2 + \frac{x_k}{1-x_k} \tag{3}$$ where the sum on the LHS is now independent on $k$ and we can consider it as a constant $c$. We now sum (3) from $k=1$ to $n$ \begin{align} nc&=\frac{\lambda}{2} \left( n - 1 + \sum_{k=1}^n x_k^2\right) + c \\ \Rightarrow \quad c&= \frac{\lambda}{2} + \frac{\lambda}{2(n-1)} \sum_{k=1}^n x_k^2 > \frac{\lambda}{2} \tag{4} \end{align} which we will need to use in a second. Rearranging Equation (3) gives a monic polynomial in $x_k$ $$x_k^3 - 3x_k^2 + \left( 3 - \frac{2+2c}{\lambda} \right)x_k + \frac{2c}{\lambda} - 1 = 0 \, . \tag{5}$$ A cubic can have either only 1 real solution, in which case there is nothing to show, since then $x_1=...=x_n$ follows, or it can have 3 real solutions. In this case there appears to be a great variety of combinations of the three roots for the various $x_k$. However, since the product of the three roots is equal to $1-\frac{2c}{\lambda}<0$ by Equation (4) and (5), either all three roots are negative (discard), or only one root is negative and we are left with two choices for the various $x_k$. But then, since the sum of all three roots is equal to $3$ by Equation (5) and one root is negative, the sum of the two positive roots must be strictly greater than $3$. This implies, that at least one of them is strictly greater than $1/2$, which stands in contradiction to Equation (2). Thus, we are left with only one valid real solution satisfying Equation (2) and $$x_1=...=x_n=x$$ follows. It is then easy to see that $x=1/2n$.

It remains to show, that this extremal point is actually a maximum. The hessian of $L$ is given in coordinates by $$\frac{1}{2} \, {\rm Hess}_{k,l} (L) = \frac{2\delta_{k,l}}{(1-x_k)^3} \sum_{i\neq k} \frac{x_i}{1-x_i} + \frac{1-\delta_{k,l}}{(1-x_k)^2(1-x_l)^2} \qquad \text{for} \qquad k,l=1,...,n \\ \frac{1}{2} \, {\rm Hess}_{n+1,k} (L) = \frac{1}{2} \, {\rm Hess}_{k,n+1} (L) = -1 \qquad \text{for} \qquad k=1,...,n \\ \frac{1}{2} \, {\rm Hess}_{n+1,n+1} (L) = 0 \, .$$ With $x_k=x=1/2n$ the first line becomes $$\frac{1}{2} \, {\rm Hess}_{k,l} (L) = \frac{1-\frac{\delta_{k,l}}{n}}{\left(1-\frac{1}{2n}\right)^4} \qquad \text{for} \qquad k,l=1,...,n$$ and in matrix-form this looks like $$\frac{1}{2} \, {\rm Hess} (L) = \frac{1}{\left(1-\frac{1}{2n}\right)^4} \begin{pmatrix} 1-1/n & 1 & \dots & 1 & -1 \\ 1 & 1-1/n & \dots & 1 & -1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & \dots & 1-1/n & -1 \\ -1 & -1 & \dots & -1 & 0 \end{pmatrix} \, .$$ Then, defining the variational vector $\epsilon=(\epsilon_1,...,\epsilon_n,\epsilon_\lambda)^t$, we find for the second variation $$\frac{1}{2} \sum_{k,l=1}^{n+1} \epsilon_k \, {\rm Hess}_{k,l} (L) \, \epsilon_l = - \frac{\sum_{k=1}^n \epsilon_k^2/n}{\left(1-\frac{1}{2n}\right)^4}<0$$ $\forall \epsilon \in {\mathbb R}^{n+1}$ satisfying $$\sum_{k=1}^n \epsilon_k = 0 \, ,$$ which is a consequence of Equation (2).

$\endgroup$
3
  • $\begingroup$ I'm not familiar with lagrange multipliers. Are you sure there is no other method using Jensen or tangent line? $\endgroup$
    – PNT
    May 15 at 13:50
  • $\begingroup$ Probably there must be some trivial solution, if I interpret @G Cab's "hint" correctly, but unfortunately he doesn't want to share ;). While his hint is pretty obvious, it did not help me in any way to find such simple solution. Lagrange multipliers is the first thing I think of, when trying to maximize/minimize something, given a constraint. $\endgroup$
    – Diger
    May 15 at 14:14
  • $\begingroup$ +1. Nice Lagrange multiplier proof. $\endgroup$
    – Hans
    May 23 at 1:07
1
$\begingroup$

Hint:

Indicating as $S_n , \, T_n$ $$ \begin{array}{l} T_n = \sum\limits_{1 \le i < j \le n} {a_i a_j } \\ S_n = \sum\limits_{1 \le i,j \le n} {a_i a_j } = \sum\limits_{1 \le i \le n} {\sum\limits_{1 \le j \le n} {a_i a_j } } = \sum\limits_{1 \le i \le n} {a_i } \sum\limits_{1 \le j \le n} {a_j } = \left( {\sum\limits_{1 \le i \le n} {a_i } } \right)^2 \\ \end{array} $$ then you also have that $$ \begin{array}{l} S_n = \sum\limits_{1 \le i,j \le n} {a_i a_j } = \sum\limits_{1 \le i < j \le n} {a_i a_j } + \sum\limits_{1 \le i = j \le n} {a_i a_j } + \sum\limits_{1 \le j < i \le n} {a_i a_j } = \\ = 2T_n + \sum\limits_{1 \le i \le n} {a_i ^2 } \\ \end{array} $$

$\endgroup$

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.