Karamata's Inequality: Difference between revisions
m ` |
Proof of the Inequality |
||
| Line 20: | Line 20: | ||
Then, assuming <math>a_i\geq a_{i+1}</math> and similarily with the <math>b_i</math>'s, we get that <math>c_i\geq c_{i+1}</math>. Now, we know: | Then, assuming <math>a_i\geq a_{i+1}</math> and similarily with the <math>b_i</math>'s, we get that <math>c_i\geq c_{i+1}</math>. Now, we know: | ||
<cmath>\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)</cmath> | <cmath>\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})</cmath><cmath>\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)</cmath><cmath>\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</cmath>. | ||
Therefore, | |||
<cmath>\sum_{i=1}^{n}f(a_i) \geq \sum_{i=1}^{n}f(b_i)</cmath> | |||
Now, we know that | Now, we know that | ||
Revision as of 13:31, 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})\]](http://latex.artofproblemsolving.com/3/e/6/3e64c9146d7841436de40d5d5e72757978fdafe3.png)
![\[\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)\]](http://latex.artofproblemsolving.com/c/b/a/cba4bc41c9d0d35b27b8ce9431c6c5d39c3f9cf1.png)
![\[\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\]](http://latex.artofproblemsolving.com/2/0/f/20f7bb1eec5a949d486b9af2e333b6b195dbaa1b.png)
.
Therefore,
![\[\sum_{i=1}^{n}f(a_i) \geq \sum_{i=1}^{n}f(b_i)\]](http://latex.artofproblemsolving.com/a/5/f/a5f3a0bda5405595d581b32b1825d4126963bd36.png)
Now, we know that This article is a stub. Help us out by expanding it.
