# 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}$

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

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

Edit:

I'll present my best bound yet on $$\sum_{1\le i 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$$

• From a math olympiad, I'll post the original problem just wait a minute.
– PNT
May 7 at 20:37
• Is it from an active (on-going) contest? In that case see math.meta.stackexchange.com/q/16774/42969 May 7 at 20:52
• No, you can read the date in the paper. It says 6 May so it's yesterday
– PNT
May 7 at 20:53
• @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 May 8 at 9:24
• It’s aimed for high school students, for knowledge I think it requires just basic inequalities like CS or AM-GM. @Dr.Mathva
– PNT
May 8 at 12:26

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 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...

• Nitpicking: As I understand it, the used “AC method” requires the domain $S$ to be compact. May 8 at 14:45
• I'm confused... Don't we want to prove $\leq \frac{k(k-1)}{2(2k-1)^2}$? May 13 at 12:21
• +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.
– Hans
May 16 at 1:24
• 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? May 16 at 13:36
• @Diger: Did you see Lemma 2.1-2.3 in ijpam.eu/contents/2012-80-3/6/6.pdf?
– Hans
May 16 at 20:09

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

• I'm not familiar with lagrange multipliers. Are you sure there is no other method using Jensen or tangent line?
– PNT
May 15 at 13:50
• 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. May 15 at 14:14
• +1. Nice Lagrange multiplier proof.
– Hans
May 23 at 1:07

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