Let the integer $n \ge 2$, and the real numbers $x_1,x_2,\cdots,x_n\in \left[0,1\right] $.Prove that\[\sum_{1\le k<j\le n} kx_kx_j\le \frac{n-1}{3}\sum_{k=1}^n kx_k.\]
Problem
Source: China Lanzhou 17 Aug 2013
Tags: induction, inequalities proposed, inequalities
MathUniverse
17.08.2013 17:55
It can be easily proved using induction. Excuse me for comment like this, but I'm writing this using mobile phone so it's hard to write in latex.
DVDthe1st
17.08.2013 19:38
In fact no need for induction, if you have good algebraic visualization skills. For $n=2$: $x_1x_2\le\min\{x_1,x_2\}\le\frac{1}{3}(x_1+2x_2)$. We use this as a lemma: \[\displaystyle\sum_{1\le k<j\le n}kx_kx_j\le \displaystyle\sum_{1\le k<j\le n}\frac{k}{3}(x_k+2x_j)=\frac{n-1}{3}\displaystyle\sum^n_{k=1}kx_k\]
chxris
25.08.2013 11:30
We can use AM-GM and the fact $x_{i} \in [0,1]$ for $1 \leq i \leq n$: \[\frac{1}{3}(ax_{a}+2ax_{b}) \geq a\sqrt[3]{x_{a}x_{b}^2} \geq ax_{a}x_{b}\] Then, sum it all up for all $1 \leq a < b \leq n$, we have the desired inequality.
HamstPan38825
06.07.2022 05:41
Induct on $n$. When $n=2$, write $$x_1x_2 = \frac 13(x_1x_2+x_1x_2) \leq \frac 13(x_1+2x_2).$$For the inductive step, write \begin{align*} \sum_{k < \ell \leq n} kx_kx_\ell &= \sum_{k < \ell \leq n-1} kx_k x_\ell + x_n \sum_{k<n} kx_k \\ &\leq \frac{n-4}3 \sum_{k < n} kx_k + \sum_{k < n} k\left(\frac 13 x_k + \frac 23 x_n\right) \\ &\leq \frac{n-4} 3 \sum_{k < n} kx_k + \frac 13 \sum_{k < n} kx_k + \frac{n(n-1)}3 x_n \\ &= \frac{n-1}3 \sum_{k \leq n} kx_k, \end{align*}as required.
pud
16.05.2024 04:33
We can make $x_k$ be 0 or 1 because all functions with respect to $x_k$ are linear. This adjustment can greatly simplify the problem
Suan_16
22.05.2024 15:06
@ pud but you don't know whether the coefficients are positive or negative, thus requiring classification
which is nearly impossible to do while n
pud
23.05.2024 17:03
Suan_16 wrote: @ pud but you don't know whether the coefficients are positive or negative, thus requiring classification
which is nearly impossible to do while n
Why? The functions are linearly, so no matter what the coefficients are positive or negative, the extreme values are all at the endpoint that is 0 or 1.
Suan_16
27.05.2024 15:21
pud wrote: Suan_16 wrote: @ pud but you don't know whether the coefficients are positive or negative, thus requiring classification
which is nearly impossible to do while n
Why? The functions are linearly, so no matter what the coefficients are positive or negative, the extreme values are all at the endpoint that is 0 or 1. of course the extreme values are at 0 or 1 sum(1<=k<j<=n)(k*xk*xj)<=(n-1)/3*(sum)(n)(i=1)(k*xk) is Equivalent to (n-1)/3*(sum)(n)(i=1)(k*xk)-sum(1<=k<j<=n)(k*xk*xj)>=0, and for all functions to xk is linear and to prove if it's >=0 requires to find some sort of minimum but:if coefficient>0,than xk=0 is what we want if coefficient<0,than xk=1 is what we want this is classification(if n:classify in 2^n types)
I can't understand, as a linear function f(x)=mx+n, if you want to find the minimum in [a,b] you have to classify
m>0:min=f(a),m<0:min=f(b),do you think that you can just use min{f(a),f(b)}?
pud
01.06.2024 17:42
Suan_16 wrote: pud wrote: Suan_16 wrote: @ pud but you don't know whether the coefficients are positive or negative, thus requiring classification
which is nearly impossible to do while n
Why? The functions are linearly, so no matter what the coefficients are positive or negative, the extreme values are all at the endpoint that is 0 or 1. of course the extreme values are at 0 or 1 sum(1<=k<j<=n)(k*xk*xj)<=(n-1)/3*(sum)(n)(i=1)(k*xk) is Equivalent to (n-1)/3*(sum)(n)(i=1)(k*xk)-sum(1<=k<j<=n)(k*xk*xj)>=0, and for all functions to xk is linear and to prove if it's >=0 requires to find some sort of minimum but:if coefficient>0,than xk=0 is what we want if coefficient<0,than xk=1 is what we want this is classification(if n:classify in 2^n types)
I can't understand, as a linear function f(x)=mx+n, if you want to find the minimum in [a,b] you have to classify
m>0:min=f(a),m<0:min=f(b),do you think that you can just use min{f(a),f(b)}?
That's enough. What I mean is, we don't need to care whether the coefficient is positive or negative, when the extreme values are both 0 or 1. So we can purpose $x_k \in \{0, 1\}$.
Because we don't know if the coefficient is positive or negative, we can only adjust $x_k $to 0 or 1, but we don't know if it's specifically 0 or 1.
Suan_16
05.06.2024 08:03
pud wrote: Suan_16 wrote: pud wrote: Why? The functions are linearly, so no matter what the coefficients are positive or negative, the extreme values are all at the endpoint that is 0 or 1. of course the extreme values are at 0 or 1 sum(1<=k<j<=n)(k*xk*xj)<=(n-1)/3*(sum)(n)(i=1)(k*xk) is Equivalent to (n-1)/3*(sum)(n)(i=1)(k*xk)-sum(1<=k<j<=n)(k*xk*xj)>=0, and for all functions to xk is linear and to prove if it's >=0 requires to find some sort of minimum but:if coefficient>0,than xk=0 is what we want if coefficient<0,than xk=1 is what we want this is classification(if n:classify in 2^n types)
I can't understand, as a linear function f(x)=mx+n, if you want to find the minimum in [a,b] you have to classify
m>0:min=f(a),m<0:min=f(b),do you think that you can just use min{f(a),f(b)}?
That's enough. What I mean is, we don't need to care whether the coefficient is positive or negative, when the extreme values are both 0 or 1. So we can purpose $x_k \in \{0, 1\}$.
Because we don't know if the coefficient is positive or negative, we can only adjust $x_k $to 0 or 1, but we don't know if it's specifically 0 or 1.
Oh I see what you means, it can be $0$ or $1$ but we don't know what it is exactly Sorry for my misunderstanding