1
$\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
  • 2
    $\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 '19 at 7:59
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.