Prove Inequality: Nonnegative Reals {x}_{1}...{x}_{n} Sum to 1

[Mathick]

There are nonnegative real numbers \(\displaystyle {x}_{1}, {x}_{2}, ... , {x}_{n}\) such that \(\displaystyle {x}_{1} + {x}_{2} +...+ {x}_{n} =1 \) where \(\displaystyle n \ge 2\). Prove that

\(\displaystyle \max\left\{{x}_{1},{x}_{2},...,{x}_{n}\right\} \cdot (1+2 \cdot \sum_{1\le i<j\le n}^{}\min\left\{{x}_{i}, {x}_{j}\right\}) \ge 1 \).

I noticed that for \(\displaystyle n=2\) there are \(\displaystyle {x}_{1} + {x}_{2} = 1\) and, not decreasing generality of the task, I assumed that \(\displaystyle {x}_{1} \le {x}_{2}\) . Because sum of two element is equal 1, so one of them must be less or equal \(\displaystyle \frac{1}{2}\) and the other one must be bigger or equal \(\displaystyle \frac{1}{2}\). So \(\displaystyle 0 \le {x}_{1} \le \frac{1}{2} \le {x}_{2} \le 1\). Hence

\(\displaystyle \max\left\{{x}_{1},{x}_{2}\right\} \cdot (1+2 \cdot \sum_{1\le i<j\le 2}^{}\min\left\{{x}_{i}, {x}_{j}\right\})={x}_{2} (1+2{x}_{1})={x}_{2}+2{x}_{1}{x}_{2}\ge{x}_{2}+2\cdot\frac{1}{2}\cdot{x}_{1}={x}_{2}+{x}_{1}=1\)

But now I don't know how to prove it for n elements. Please help!

 

[Opalg]

There are nonnegative real numbers \(\displaystyle {x}_{1}, {x}_{2}, ... , {x}_{n}\) such that \(\displaystyle {x}_{1} + {x}_{2} +...+ {x}_{n} =1 \) where \(\displaystyle n \ge 2\). Prove that

\(\displaystyle \max\left\{{x}_{1},{x}_{2},...,{x}_{n}\right\} \cdot (1+2 \cdot \sum_{1\le i<j\le n}^{}\min\left\{{x}_{i}, {x}_{j}\right\}) \ge 1 \).

I noticed that for \(\displaystyle n=2\) there are \(\displaystyle {x}_{1} + {x}_{2} = 1\) and, not decreasing generality of the task, I assumed that \(\displaystyle {x}_{1} \le {x}_{2}\) . Because sum of two element is equal 1, so one of them must be less or equal \(\displaystyle \frac{1}{2}\) and the other one must be bigger or equal \(\displaystyle \frac{1}{2}\). So \(\displaystyle 0 \le {x}_{1} \le \frac{1}{2} \le {x}_{2} \le 1\). Hence

\(\displaystyle \max\left\{{x}_{1},{x}_{2}\right\} \cdot (1+2 \cdot \sum_{1\le i<j\le 2}^{}\min\left\{{x}_{i}, {x}_{j}\right\})={x}_{2} (1+2{x}_{1})={x}_{2}+2{x}_{1}{x}_{2}\ge{x}_{2}+2\cdot\frac{1}{2}\cdot{x}_{1}={x}_{2}+{x}_{1}=1\)

But now I don't know how to prove it for n elements. Please help!

Hi Mathick, and thanks for setting such a challenging problem in your first post for MHB!I'l start by assuming, as you do, that $x_1 \leqslant x_2\leqslant \ldots \leqslant x_n$, so that $$\begin{aligned} \max\{x_1,\ldots,x_n\}\Bigl(1 + 2\!\!\!\sum_{1\leqslant i<j\leqslant n}\min\{x_i,x_j\}\Bigr) &= x_n\bigl(1 + 2x_{n-1} + 4x_{n-2} + \ldots (2n-2)x_1\bigl) \\ &= (1 - x_1 - x_2 - \ldots x_{n-1}) \bigl(1 + 2x_{n-1} + 4x_{n-2} + \ldots (2n-2)x_1\bigl) \overset{\mathrm{def}}{=} f(x_1,x_2,\ldots,x_{n-1}). \end{aligned}$$We want to show that $f(x_1,x_2,\ldots,x_{n-1}) \geqslant 1$ whenever $0 \leqslant x_1\leqslant x_2 \leqslant \ldots \leqslant x_{n-1} \leqslant 1 - x_1 - x_2 - \ldots - x_{n-1}.$ You have already proved this for the case $n=2$. I have a proof for $n=3$. But I am sure that there should be a better method, because my method does not give any clue about proving the result for larger values of $n$.When $n=3$ we have the function $f(x_1,x_2) = (1-x_1 - x_2)(1+ 4x_1 + 2x_2)$, defined in the triangular region given by the inequalities $0\leqslant x_1\leqslant x_2 \leqslant 1 - x_1 - x_2$.Notice that $x_1$ must lie between $0$ and $x_2$. Suppose that we keep $x_2$ fixed and regard $f(x_1,x_2)$ as a function of $x_1$. Its second partial derivative $\frac{\partial^2f}{\partial x_1^2}$ is $-8$, which is negative. Therefore $f(x_1,x_2)$ is convex downwards on the interval $[0,x_2]$ and hence attains its minimum value at an endpoint of the interval.If $x_1 = 0$ then $x_1$ makes no contribution to $f(x_1,x_2)$. By applying your result for the 2-dimensional case, we can conclude that $f(x_1,x_2) \geqslant 1$ when $x_1 = 0.$If $x_1 = x_2$ then the function $f(x_2,x_2)$ becomes $(1 - 2x_2)(1 + 6x_2)$, which is again convex downwards and hence attains its minimum value at an endpoint of the interval. We have already dealt with what happens at the lower end of this interval. The upper end is when $x_1=x_2$ has the maximum possible value, which is when $x_1 = x_2 = x_3 = \frac13$. At that point, $f(x_1,x_2) = 1$. Thus $f(x_1,x_2) \geqslant 1$ throughout its domain, and attains the minimum value $1$ at the points $(x_1,x_2,x_3) = \bigl(\frac13,\frac13,\frac13\bigr)$, $\bigl(0,\frac12,\frac12\bigr)$ and $(0,0,1)$.In the general case, the domain of $f(x_1,x_2,\ldots,x_{n-1})$ is given by the inequalities $0 \leqslant x_1\leqslant x_2 \leqslant \ldots \leqslant x_{n-1} \leqslant 1 - x_1 - x_2 - \ldots - x_{n-1}.$ This set is a simplex, with vertices corresponding to $$ (x_1,x_2,\ldots,x_n) = \bigl(\overbrace{0,\ldots,0}^r,\overbrace{\tfrac1{n-r}, \ldots, \tfrac1{n-r} }^{n-r}\bigr) \qquad(0 \leqslant r \leqslant n-1).$$ It seems to me that these must be exactly the points at which $f(x_1,x_2,\ldots,x_{n-1}) = 1$, and that it must be greater than $1$ everywhere else. But I am no closer to finding a proof for that. (Headbang)