Proof of an inequality that seems intuitive

Question

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?

Denote $\mathbf x=(x_1,\ldots,x_n)$, $\mathbf a=(a_1,\ldots,a_n)$ and $\mathbf 1_m=(\underbrace{1,\ldots,1}{\text{$m$ times}},\underbrace{0,\ldots,0}{\text{$n-m$ times}})$. You want to prove that $\langle\mathbf a,\mathbf x\rangle \le \langle\mathbf 1_m,\mathbf x\rangle$. It is sufficient to show that $\langle\mathbf a,\mathbf 1_k\rangle \le \langle\mathbf 1_m,\mathbf 1_k\rangle$ for all $k$, because $\mathbf x$ is a positive linear combination of $\mathbf 1_k$. — , Dec 20 '15 at 07:44
Another post about the same inequality: Proving the inequality: $\sum_{i=1}^{n}q_i r_i \leq \sum_{i=1}^k r_i$. — Martin Sleziak, Feb 18 '19 at 12:28
A post on MathOverflow about very similar inequality: Does anyone recognize this inequality? — Martin Sleziak, Feb 18 '19 at 17:51

score 1 · Answer 1 · answered Dec 20 '15 at 08:10

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}

score 1 · Accepted Answer · answered Dec 20 '15 at 16:58

\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*}

score 0 · Answer 3 · answered Dec 20 '15 at 15:07

Let's smooth the values of $a_i$ to get the bound.

Replace $(a_k,a_{k+1})$ with $(\min(1,a_k+a_{k+1}), \max(0, a_k+a_{k+1}-1))$.

Then, we look at the terms which are affected.

$$(\min(1,a_k+a_{k+1})x_k+\max(0, a_k+a_{k+1}-1)x_{k+1})-(a_kx_k+a_{k+1}x_{k+1})\\ =\min(1-a_k,a_{k+1})x_k+\max(-a_{k+1}, a_k-1)x_{k+1}\\ =\min(1-a_k,a_{k+1})x_k-\min(1-a_k,a_{k+1})x_{k+1}\\ =\min(1-a_k,a_{k+1})(x_k-x_{k+1})\geq0$$

Hence, this increases the value of the left-hand side.

We do this replacement until doing it cannot change the $a_i$. In that case, we have for all $k$, either $a_k=1$ or $a_{k+1}=0$.

Take the first $k$ such that $a_{k+1}=0$, increase $a_k$ to $1$. It is easy to see here, $k=m$, if $m$ assumes it's minimum possible value. Now the left-hand side is equal to the right-hand side, and we are done.

Proof of an inequality that seems intuitive

3 Answers3

Linked