Difference between revisions of "Karamata's Inequality"
(Proof of the Inequality) |
(→Proof) |
||
| (6 intermediate revisions by 4 users not shown) | |||
| Line 5: | Line 5: | ||
==Proof== | ==Proof== | ||
We will first use an important fact: | We will first use an important fact: | ||
| − | < | + | If <math>f(x)</math> is convex over the interval <math>(a, b)</math>, then <math>\forall a\leq x_1\leq x_2 \leq b</math> and <math>\Gamma(x, y):=\frac{f(y)-f(x)}{y-x}</math>, <math>\Gamma(x_1, x)\leq \Gamma (x_2, x)</math> |
This is proven by taking casework on <math>x\neq x_1,x_2</math>. If <math>x<x_1</math>, then | This is proven by taking casework on <math>x\neq x_1,x_2</math>. If <math>x<x_1</math>, then | ||
| Line 22: | Line 22: | ||
<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>. | <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, | + | Therefore, <cmath>\sum_{i=1}^{n}f(a_i) \geq \sum_{i=1}^{n}f(b_i)</cmath> |
| − | <cmath>\sum_{i=1}^{n}f(a_i) \geq \sum_{i=1}^{n}f(b_i)</cmath> | + | |
| + | Thus, we have proven Karamata's Theorem. | ||
| + | |||
| − | |||
{{stub}} | {{stub}} | ||
==See also== | ==See also== | ||
| − | [[Category: | + | |
| − | [[Category: | + | [[Category:Algebra]] |
| + | [[Category:Inequalities]] | ||
Latest revision as of 02:39, 28 March 2024
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:
If 
is convex over the interval 
, then 
and 
, 
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)
Thus, we have proven Karamata's Theorem.
This article is a stub. Help us out by expanding it.
