2
$\begingroup$

Given $x=[x_1\quad x_2\quad \ldots \quad x_n],$ such that $x_1\geq x_2\geq\cdots\geq x_n$. Prove the following inequality:

\begin{equation} x_1+x_2+\cdots+x_L\geq a_1x_1+a_2x_2+\cdots+a_nx_n \end{equation}

for all $L=1,2,\ldots,n$ and $a_1+a_2+\cdots+a_n=L$ and $0\leq a_i\leq 1$.

My attempt: I understand the idea behind, on LHS we take largest $L$ elements, while on the LHS we are taking weighted sum, which will be less. But how to prove it mathematically?

\begin{equation} (1-a_1)x_1+(1-a_2)x_2+\cdots+(1-a_L)x_L\geq a_{L+1}x_{L+1}+\cdots+a_nx_n \end{equation}

Equality achieved only when $a_i=1$ for $i=1,2,\ldots,L$ and $a_i=0$ for $i=L+1,L+2,\ldots,n$, then LHS=RHS=$0$.

$\endgroup$
1
  • 3
    $\begingroup$ You are almost there. Note that $$\sum_{i=1}^L\,(1-a_i)\,x_i\geq \sum_{i=1}^L\,(1-a_i)\,x_L=\sum_{i=L+1}^n\,a_i\,x_L.$$ I leave the last step to you. $\endgroup$
    – Batominovski
    Oct 10, 2019 at 7:59

1 Answer 1

Reset to default
3
$\begingroup$

You can use the fact that $$(1-a_1)x_1+\cdots+(1-a_L)x_L\geq (1-a_1+\cdots+1-a_L)x_L$$ together with $(1-a_1+\cdots+1-a_L)-a_{L+1}-\cdots-a_n=0$.

$\endgroup$

You must log in to answer this question.

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