10
$\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, 2022 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, 2022 at 20:52
  • 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, 2022 at 9:24
  • 1
    $\begingroup$ Are you not going to accept Dr. Mathva's answer, especially considering his is the first correct answer, having introduced a general inequality proving method and not being awarded any bounty? $\endgroup$
    – Hans
    May 23, 2022 at 1:31
  • 1
    $\begingroup$ This is a highschool contest. So I'm fairly sure the official solution doesn't use his method. I want an elementary solution that I can possibly use in upcoming contests @Hans $\endgroup$
    – PNT
    May 23, 2022 at 7:49

5 Answers 5

8
$\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, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 20:09
4
$\begingroup$

I found the AoPS link https://artofproblemsolving.com/community/c6h2503722p21150538. It is a problem from "Problems From the Book", 2008, Ch. 2, which was proposed by Vasile Cartoaje. The proof there is very nice. I put the proof here.

Let us write the inequality as $$\left(\sum_{i=1}^n \frac{x_i}{1 - x_i}\right)^2 \le \sum_{i=1}^n \frac{x_i^2}{(1 - x_i)^2} + \frac{n(n-1)}{(2n-1)^2}.$$

Using Cauchy-Bunyakovsky-Schwarz inequality, we have $$\left(\sum_{i=1}^n \frac{x_i}{1 - x_i}\right)^2 \le \left(\sum_{i=1}^n x_i\right) \left(\sum_{i=1}^n \frac{x_i}{(1-x_i)^2}\right) = \sum_{i=1}^n \frac{x_i/2}{(1-x_i)^2}.$$

Thus, it suffices to prove that $$\sum_{i=1}^n \frac{x_i/2}{(1-x_i)^2} \le \sum_{i=1}^n \frac{x_i^2}{(1 - x_i)^2} + \frac{n(n-1)}{(2n-1)^2}$$ or $$\sum_{i=1}^n \frac{x_i(1 - 2x_i)}{(1-x_i)^2} \le \frac{2n(n-1)}{(2n-1)^2}.$$

Note that $x \mapsto \frac{x(1-2x)}{(1-x)^2}$ is concave on $[0, 1/2]$. Using Jensen's inequality, the desired result follows.

$\endgroup$
4
  • $\begingroup$ I didn’t expect seeing a problem from this Book in a math olympiad contest. $\endgroup$
    – PNT
    Jun 2, 2022 at 13:22
  • $\begingroup$ @PNT Yes. Also, it seems an old problem according to the book. $\endgroup$
    – River Li
    Jun 2, 2022 at 13:27
  • $\begingroup$ I expected such a proof, but thanks very much for sharing. $\endgroup$
    – Diger
    Jul 2, 2022 at 11:02
  • $\begingroup$ @Diger Thanks. The proof uses calculus. My second proof uses no calculus. $\endgroup$
    – River Li
    Jul 2, 2022 at 12:06
4
+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
  • 1
    $\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, 2022 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, 2022 at 14:14
  • $\begingroup$ +1. Nice Lagrange multiplier proof. $\endgroup$
    – Hans
    May 23, 2022 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$
1
$\begingroup$

My second proof: without using calculus

We use the following bound: $$\frac{x_ix_j}{(1-x_i)(1-x_j)} \le \frac{1}{(2n-1)^4} + \frac{16n^2(n-1)^2}{(2n-1)^4}\cdot \frac{x_ix_j}{1-x_i-x_j}. \tag{1}$$ (See Remarks at the end for details.)

Taking $\sum_{1\le i < j \le n}$ on (1), it suffices to prove that $$\frac{1}{(2n-1)^4}\cdot \frac{n(n-1)}{2} + \frac{16n^2(n-1)^2}{(2n-1)^4}\sum_{1\le i < j \le n} \frac{x_ix_j}{1-x_i-x_j} \le \frac{n(n-1)}{2(2n-1)^2} $$ or $$\sum_{1\le i < j \le n} \frac{x_ix_j}{1-x_i-x_j} \le \frac18. \tag{2}$$

@Sangchul Lee gave a very nice proof for (2) as follows (I rewrote it compactly). See: Prove or disprove $\sum\limits_{1\le i < j \le n} \frac{x_ix_j}{1-x_i-x_j} \le \frac18$ for $\sum\limits_{i=1}^n x_i = \frac12$($x_i\ge 0, \forall i$)

WLOG, assume that $x_i < 1/2$ for all $i$.

Using Cauchy-Bunyakovsky-Schwarz inequality, we have $$\left(\frac{1}{1/2 - x_i} + \frac{1}{1/2 - x_j}\right)(1/2 - x_i + 1/2 - x_j) \ge 4$$ which results in $$\frac{1}{1 - x_i - x_j} \le \frac14\left(\frac{1}{1/2 - x_i} + \frac{1}{1/2 - x_j}\right) = \frac{1}{2 - 4x_i} + \frac{1}{2 - 4x_j}.$$ Thus, we have \begin{align*} \sum_{1\le i < j \le n} \frac{x_ix_j}{1-x_i-x_j} &\le \sum_{1\le i < j \le n} \left(\frac{1}{2 - 4x_i} + \frac{1}{2 - 4x_j}\right)x_ix_j \\ &= \frac12 \sum_{i, j : \, i\ne j} \left(\frac{1}{2 - 4x_i} + \frac{1}{2 - 4x_j}\right)x_ix_j \qquad\qquad (\mathrm{symmetry})\\ &= \frac12\left[\sum_{i,j} \left(\frac{1}{2 - 4x_i} + \frac{1}{2 - 4x_j}\right)x_ix_j - \sum_{i=1}^n \frac{2x_i^2}{2 - 4x_i} \right]\\ &= \frac12\left[\sum_{i=1}^n \frac{x_i}{2 - 4x_i}\sum_{j=1}^n x_j + \sum_{i=1}^n x_i \sum_{j=1}^n \frac{x_j}{2-4x_j}- \sum_{i=1}^n \frac{2x_i^2}{2 - 4x_i} \right]\\ &= \frac12\left[\frac12\sum_{i=1}^n \frac{x_i}{2 - 4x_i} + \frac12 \sum_{j=1}^n \frac{x_j}{2-4x_j}- \sum_{i=1}^n \frac{2x_i^2}{2 - 4x_i} \right]\\ &= \frac12\sum_{i=1}^n \left(\frac12 \frac{x_i}{2 - 4x_i} + \frac12 \frac{x_i}{2-4x_i}- \frac{2x_i^2}{2 - 4x_i} \right)\\ &= \frac12 \sum_{i=1}^n \frac{x_i}{2}\\ &= \frac18. \tag{3} \end{align*}

We are done.


Remarks:

The idea behind (1) is given as follows.

First, when $x_1 = x_2 = \cdots = x_n = \frac{1}{2n}$, the original inequality occurs with equality. When $x_i = x_j = \frac{1}{2n}$, we have $x_ix_j/(1-x_i-x_j) = \frac{1}{4n(n-1)}$. Using $\frac{1}{1+u} \ge \frac{1}{1+v} - \frac{1}{(1+v)^2}(u-v)$ for $u = x_ix_j/(1-x_i-x_j)$ and $v=\frac{1}{4n(n-1)}$, we have \begin{align*} \frac{x_ix_j}{(1-x_i)(1-x_j)} &= 1 - \frac{1}{1 + x_ix_j/(1-x_i-x_j)}\\ &\le \frac{1}{(2n-1)^4} + \frac{16n^2(n-1)^2}{(2n-1)^4}\cdot \frac{x_ix_j}{1-x_i-x_j}. \end{align*}

$\endgroup$
2
  • $\begingroup$ How do you prove $$\frac{1}{1 - u - v} \le \frac14(\frac{1}{1/2 - u} + \frac{1}{1/2 - v})$$ using CS? I see that this is the AM-HM inequality, but not sure about CS. $\endgroup$
    – Diger
    Jul 2, 2022 at 11:15
  • 1
    $\begingroup$ @Diger It is just $\left(\frac{1}{1/2 - u} + \frac{1}{1/2 - v}\right)(1/2 - u + 1/2 - v) \ge 4$. $\endgroup$
    – River Li
    Jul 2, 2022 at 11:59

You must log in to answer this question.

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