Difference between revisions of "Karamata's Inequality"

(New page: '''Karamata's Inequality''' states that if <math>(x_i)</math> majores <math>(y_i)</math> and <math>f</math> is a convex function, then <center><math>\sum_{i=1}^{n}f(x...)
 
m
(7 intermediate revisions by 5 users not shown)
Line 1: Line 1:
'''Karamata's Inequality''' states that if <math>(x_i)</math> [[Majorization|majores]] <math>(y_i)</math> and <math>f</math> is a [[convex function]], then
+
'''Karamata's Inequality''' states that if <math>(a_i)</math> [[Majorization|majorizes]] <math>(b_i)</math> and <math>f</math> is a [[convex function]], then
  
<center><math>\sum_{i=1}^{n}f(x_i)\geq \sum_{i=1}^{n}f(y_i)</math></center>
+
<cmath>\sum_{i=1}^{n}f(a_i)\geq \sum_{i=1}^{n}f(b_i)</cmath>
  
 
==Proof==
 
==Proof==
{{incomplete|proof}}
+
We will first use an important fact:
 +
<cmath>\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)</cmath>
 +
 
 +
This is proven by taking casework on <math>x\neq x_1,x_2</math>. If <math>x<x_1</math>, then
 +
<cmath>\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)</cmath>
 +
 
 +
A similar argument shows for other values of <math>x</math>.
 +
 
 +
Now, define a sequence <math>C</math> such that:
 +
<cmath>c_i=\Gamma(a_i, b_i)</cmath>
 +
 
 +
Define the sequences <math>A_i</math> such that
 +
<cmath>A_i=\sum_{j=1}^{i}a_j, A_0=0</cmath>
 +
and <math>B_i</math> similarly.
 +
 
 +
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})</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>
 +
 
 +
Thus we have proven Karamata`s Theorem
 +
{{stub}}
  
 
==See also==
 
==See also==
[[Category:Theorems]]
+
 
 
[[Category:Algebra]]
 
[[Category:Algebra]]
 +
[[Category:Inequalities]]

Revision as of 16:48, 29 December 2021

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<x_1$, 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)\]

Thus we have proven Karamata`s Theorem This article is a stub. Help us out by expanding it.

See also