I posed [this question on math.stackexchange.com](https://math.stackexchange.com/q/4279365/64809) 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.



A sufficient condition for weak majorization from below
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.


