Proof of an inequality that seems intuitive

I'm looking for a short proof of the following statement:

Let $x_1 \ge \cdots \ge x_n \ge 0$ and let $0 \le a_1,\dots,a_n \le 1$. If $\sum_{k=1}^n a_k \le m$ for some integer $m$, then $$\sum_{k=1}^n a_k x_k \le \sum_{k=1}^m x_k.$$

My intuition for this is that the weights $a_1,\dots,a_n$ can be "redistributed" or "shifted" forward so that $a_k=0$ for $k>m$. It's not too hard to turn this into a proof by induction that implements such an algorithm. But a rigorous proof ends up being pretty long even though the statement seems simple.

Has anyone seen this before, and is there a shorter (possibly less algorithmic) approach?

Solution 1:

\begin{align*}\sum\limits_{k=1}^{n}{a_kx_k}&=\sum\limits_{k=1}^{m}{a_kx_k} + \sum\limits_{k=m+1}^{n}{a_kx_k} \\ &\le\sum\limits_{k=1}^{m}{a_kx_k}+\sum\limits_{k=m+1}^{n}{a_kx_m}\\ &\le\sum\limits_{k=1}^{m}{a_kx_k}+x_m\left(m-\sum\limits_{k=1}^{m}{a_k}\right)\\ &=\sum\limits_{k=1}^{m}{a_kx_k}+\sum\limits_{k=1}^{m}{(1-a_k)x_m}\\ &\le\sum\limits_{k=1}^{m}{a_kx_k}+\sum\limits_{k=1}^{m}{(1-a_k)x_k}\\ &=\sum\limits_{k=1}^{m}{x_k}. \end{align*}

Solution 2:

I think I found a short proof using the idea in Rahul's comment:

\begin{align} \sum_{k=1}^n x_k a_k &= \sum_{k=1}^{n-1} (x_k-x_{k+1}) \sum_{j=1}^k a_j + x_n\sum_{j=1}^n a_j \\ &= \sum_{k=1}^{m} (x_k-x_{k+1}) \sum_{j=1}^k a_j + \sum_{k=m+1}^{n-1} (x_k-x_{k+1}) \sum_{j=1}^k a_j + x_n\sum_{j=1}^n a_j \\ &\le \sum_{k=1}^{m} (x_k-x_{k+1})k + \sum_{k=m+1}^{n-1} (x_k-x_{k+1})m + x_n m \\ &= \sum_{k=1}^n x_n \end{align}