A sufficient condition for weak majorization from below

Question

I posed this question on math.stackexchange.com but have gotten no answer. So I post the question here in order to obtain an answer.

---

$\forall x\in \mathbf R^{n+1}$, let $x_{(0)}\le x_{(1)}\le\,\cdots\le x_{(n)}$ denote the non-decreasing rearrangement of $x$. Suppose $x,y\in\mathbf R^{n+1}$, $$\sum_{i=0}^k x_{i}\le \sum_{i=0}^k y_{i},\quad \forall k\in\{0,1,2,\cdots,n\} \tag1$$ and $$x_{i-1}\le y_i,\quad\forall i\in\{1,2,\cdots,n\}. \tag2$$ Show $$\sum_{i=0}^k x_{(i)}\le \sum_{i=0}^k y_{(i)},\quad \forall k\in\{0,1,2,\cdots,n\}.$$

---

Here is my attempt at the proof with one obstacle I fail to overcome.

Let $l_i$ be the permutation of $\{0,1,2,\cdots,n\}$ such that $y_{(i)}=y_{l_i},\, \forall i\in\{0,1,2,\cdots,n\}$. For any $k\in\{1,2,\cdots,n\}$, $$\sum_{i=0}^k (y_{(i)}-x_{(i)})=I\big(0\in\{l_i|i\in\{0,1,\cdots,k\}\}\big)(y_0-x_{(k)})+\sum_{\substack{i=0\\l_i\neq0}}^k (y_{l_i}-x_{l_i-1})+\Big(\sum_{\substack{i=0\\l_i\neq0}}^k x_{l_i-1}-\sum_{i=0}^{k-1}x_{(i)}\Big)$$ where $I$ stands for the characteristic function. Every term in the first summation term on the right hand side of the above equation is nonnegative by inequality $(2)$. The term in the second parenthesis is nonnegative by virtue of the definition of $x_{(i)}$. Presumably I should use Inequality $(1)$ to show the nonnegativity of the first term of the above equation. But I do not see how.

Answer 1

We should prove that the sum of any $k$ $y$'s is not less than the sum of certain $k$ $x$'s (indeed, this property is equivalent to the condition that the sum of $k$ smallest $y$'s is not less than the sum of $k$ smallest $x$'s.) Let our $k$ $y$'s contain $y_i$'s for $i=0,1,\ldots,p$, but do not contain $y_{p+1}$ (there exists unique such $p$). Bound the sum $y_0+\ldots+y_p$ by $x_0+\ldots+x_p$ and other $y_i$'s by corresponding $x_{i-1}$'s.