# Prove that $x_1+x_2+\cdots+x_L\geq a_1x_1+a_2x_2+\cdots+a_nx_n$

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$$.

• 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. Oct 10, 2019 at 7:59

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$$.