Difference between revisions of "Karamata's Inequality"
m (`) |
m (`) |
(No difference)
| |
Revision as of 13:26, 14 August 2018
Karamata's Inequality states that if 
majorizes 
and 
is a convex function, then
![\[\sum_{i=1}^{n}f(a_i)\geq \sum_{i=1}^{n}f(b_i)\]](http://latex.artofproblemsolving.com/8/7/a/87a4a83faeec64d121a46b01a9d9e59fa1e01f1e.png)
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)\]](http://latex.artofproblemsolving.com/d/5/d/d5dc67fdc20e99120977da82aa1d3318b4d0fb39.png)
This is proven by taking casework on 
. If 
, 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)\]](http://latex.artofproblemsolving.com/5/b/a/5ba7af700eda7a71cfae06a5a6f2af0cc3e85608.png)
A similar argument shows for other values of 
.
Now, define a sequence 
such that:
![\[c_i=\Gamma(a_i, b_i)\]](http://latex.artofproblemsolving.com/b/c/4/bc4a41fcf633cc45fc4b425e36bc9dd9658122df.png)
Define the sequences 
such that
![\[A_i=\sum_{j=1}^{i}a_j, A_0=0\]](http://latex.artofproblemsolving.com/6/3/a/63ab8ca2a0e6dabd47a146d887b1aa1edb27cd16.png)
and 
similarly.
Then, assuming 
and similarily with the 
's, we get that 
. 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-B_i) - \sum_{i=1}^{n}f(b_i)\]](http://latex.artofproblemsolving.com/a/2/4/a24c5b2346bfb5ef8cad93da677d7fd51f0277b0.png)
Now, we know that This article is a stub. Help us out by expanding it.
