# Karamata's Inequality

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Karamata's Inequality states that if $(a_i)$ majorizes $(b_i)$ and $f$ is a convex function, then

$$\sum_{i=1}^{n}f(a_i)\geq \sum_{i=1}^{n}f(b_i)$$

## Proof

We will first use an important fact: $$\text{If }f(x)\text{ is convex over the interval }(a, b)\text{, then }\forall \hspace{2mm} a\leq x_1\leq x_2 \leq b \text{ and } \Gamma(x, y):=\frac{f(y)-f(x)}{y-x}, \Gamma(x_1, x)\leq \Gamma (x_2, x)$$

This is proven by taking casework on $x\neq x_1,x_2$. If $x, then $$\Gamma(x_1, x)=\frac{f(x_1)-f(x)}{x_1-x}\leq \frac{f(x_2)-f(x)}{x_2-x}=\Gamma(x_2, x)$$

A similar argument shows for other values of $x$.

Now, define a sequence $C$ such that: $$c_i=\Gamma(a_i, b_i)$$

Define the sequences $A_i$ such that $$A_i=\sum_{j=1}^{i}a_j, A_0=0$$ and $B_i$ similarly.

Then, assuming $a_i\geq a_{i+1}$ and similarily with the $b_i$'s, we get that $c_i\geq c_{i+1}$. Now, we know: $$\sum_{i=1}^{n}f(a_i) - \sum_{i=1}^{n}f(b_i)=\sum_{i=1}^{n}f(a_i)-f(b_i)=\sum_{i=1}^{n}c_i(a_i-b_i)=\sum_{i=1}^{n}c_i(A_i-A_{i-1}-B_i+B_{i+1})$$$$\sum_{i=1}^{n}c_i(A_i-A_{i-1}-B_i+B_{i+1})=\sum_{i=1}^{n}c_i(A_i-B_i) - \sum_{i=0}^{n-1}c_{i+1}(A_i-B_i)=\sum_{i=0}^{n-1}c_i(A_i-B_i) - \sum_{i=0}^{n-1}c_{i+1}(A_i-B_i)$$$$\sum_{i=0}^{n-1}c_i(A_i-B_i) - \sum_{i=0}^{n-1}c_{i+1}(A_i-B_i)=\sum_{i=1}^{n}(c_i-c_{i+1})(A_i-B_i)\geq 0$$.

Therefore, $$\sum_{i=1}^{n}f(a_i) \geq \sum_{i=1}^{n}f(b_i)$$