Karamata's inequality

Remarks

Proof idea: let $c_i$ be the slope of the chord of $f$ between $x_i$ and $y_i$, or a subderivative at $x_i$ when $x_i = y_i$. Since the slopes of a convex function increase and both sequences decrease, $c_1 \ge c_2 \ge \dots \ge c_n$. Then $\sum_i \big(f(x_i) - f(y_i)\big) = \sum_i c_i (x_i - y_i)$, and summation by parts writes this as a sum of products of the nonnegative numbers $c_k - c_{k+1}$ with the nonnegative partial sums $\sum_{i \le k} (x_i - y_i)$.

Example: $(2, 0)$ majorizes $(1, 1)$, so $f(2) + f(0) \ge 2 f(1)$, which is midpoint convexity. More generally $(x_1, \dots, x_n)$ majorizes the constant vector $(\bar x, \dots, \bar x)$ with $\bar x$ the mean, which gives Jensen's inequality with equal weights.

The equality of the total sums is needed. With $n = 1$, $f(x) = -x$, $x_1 = 1$ and $y_1 = 0$, one has $x_1 \ge y_1$ but $f(x_1) = -1 < 0 = f(y_1)$.

Going deeper

For a student

The inequality says that $x \mapsto \sum_i f(x_i)$ is a Schur-convex function whenever $f$ is convex. It contains Jensen's inequality with equal weights and implies many symmetric inequalities, for instance by comparing a vector with a less spread out one. A converse also holds: if the conclusion is true for every convex $f$, then $x$ majorizes $y$.