$\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\}. \tag3$$
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.
Fedor Petrov proved the proposition. I restate his proof in slightly more details here.
Inequality is equivalent to the statement that the sum of any $k$ $y$'s is no less than the sum of some $k$ $x$'s.
Fix a subscript $k$. Let $Y_k$ be the set of arbitrary or the smallest $k$ $y$'s. In that set, find the largest subscript $p$ such that $\{y_0,y_1,\cdots,y_p\}$ is contained in it. $$\sum_{i=0}^p x_i\le\sum_{i=0}^p y_i.$$ Let the set of the subscripts of the remaining $y$'s in $Y_k$ be $I$. $p<i, \forall i\in I$. By Inquality $(2)$, $$\sum_{i\in I}x_{i-1}\le \sum_{i\in I}y_i.$$ We have completed our proof.