Twierdzenie o ciągach jednomonotonicznych

Twierdzenie o ciągach jednomonotonicznych – jedna z podstawowych nierówności w matematyce. Można za jej pomocą dowieść wielu innych nierówności, takich jak nierówności między średnimi, nierówność Cauchy’ego-Schwarza, nierówność Czebyszewa.

Twierdzenie

Niech ciągi $(a_1,a_2,\dots ,a_n)$ oraz $(b_1,b_2,\dots ,b_n)$ liczb rzeczywistych będą jednomonotoniczne, tzn. takie, że zachodzą nierówności:

$a_1⩾a_2⩾\dots ⩾a_n$ i $b_1⩾b_2⩾\dots ⩾b_n$

lub

$a_1⩽a_2⩽\dots ⩽a_n$ i $b_1⩽b_2⩽\dots ⩽b_n.$

Wówczas prawdziwe są nierówności:

$\begin{array}{cc}& a_1{b}_1+a_2{b}_2+\dots +a_n{b}_n\\ ⩾& a_{1}b{\text{'}}_1+a_{2}b{\text{'}}_2+\dots +a_{n}b{\text{'}}_n\\ ⩾& a_1{b}_n+a_2{b}_{n-1}+\dots +a_n{b}_1\end{array}$

gdzie $(b{\text{'}}_1,b{\text{'}}_2,b{\text{'}}_3,b{\text{'}}_4,\dots ,b{\text{'}}_n)$ jest dowolną permutacją ciągu $(b_1,b_2,b_3,b_4,\dots ,b_n).$

Twierdzenie to jest prawdziwe również dla więcej niż dwóch ciągów, tak długo, jak są one tej samej monotoniczności.

Dowód

W pierwszej kolejności sformułujmy tezę poprawniej.

Twierdzenie

Niech $(a{)}_{s⩽n},$ $(b{)}_{s⩽n}$ będą ciągami o zgodnej monotoniczności długości $n$ i niech $\pi$ będzie permutacją na zbiorze $\{1,\dots ,n\}.$ Wówczas

$\begin{array}{cc}& \sum _{s=1}^n{a}_s\cdot b_s\\ ⩾& \sum _{s=1}^n{a}_s\cdot b_{\pi (s)}\\ ⩾& \sum _{s=1}^n{a}_s\cdot b_{n-s+1}\end{array}$

Skupimy się na pierwszej z nierówności, gdyż druga już z niej wynika dość łatwo. Dowód będzie indukcyjny

Oczywiście dla ciągów o długości jeden teza jest oczywista.

Załóżmy zatem, że dowodzona nierówność zachodzi dla ciągów długości $n$ i niech $(a{)}_{s⩽n+1},$ $(b{)}_{s⩽n+1}$ będą ciągami o zgodnej monotoniczności długości $n+1.$ Niech ponadto $\pi$ będzie permutacją zbioru $\{1,\dots ,n+1\}.$ Jeśli $\pi (n+1)=n+1,$ to ${\pi }^{\star }=\pi {|}_{\{1,\dots ,n\}}$ jest permutacją zbioru $\{1,\dots ,n\}$ i wówczas

$\begin{array}{cc}\sum _{s=1}^{n+1}{a}_s\cdot b_s& =a_{n+1}\cdot b_{n+1}+\sum _{s=1}^n{a}_s\cdot b_s\\ & ⩾a_{n+1}\cdot b_{n+1}+\sum _{s=1}^n{a}_s\cdot b_{{\pi }^{\star }(s)}\\ & =a_{n+1}\cdot b_{\pi (n+1)}+\sum _{s=1}^n{a}_s\cdot b_{\pi (s)}\\ & =\sum _{s=1}^{n+1}{a}_s\cdot b_{\pi (s)}\end{array}$

Załóżmy zatem, że $i={\pi }^{-1}(n+1),j=\pi (n+1)\ne n+1$ i niech dla $s\in \{1,\dots ,n\}$

${\pi }^{\star }(s)=\{\begin{array}{cc}j& s=i\\ \pi (s)& s\ne i\end{array}$

Oczywiście ${\pi }^{\star }$ jest permutacją na zbiorze $\{1,\dots ,n\}.$

Ponadto mamy

$\begin{array}{cc}\sum _{s=1}^{n+1}{a}_s{b}_s& =a_{n+1}{b}_{n+1}+\sum _{s=1}^n{a}_s{b}_s\\ & ⩾a_{n+1}{b}_{n+1}+\sum _{s=1}^n{a}_s{b}_{{\pi }^{\star }(s)}\end{array}$

oraz

$\begin{array}{cc}& (a_{n+1}{b}_{n+1}+\sum _{s=1}^n{a}_s{b}_{{\pi }^{\star }(s)})-\sum _{s=1}^{n+1}{a}_s{b}_{\pi (s)}\\ =& (a_{n+1}{b}_{n+1}+\sum _{s=1}^n{a}_s{b}_{{\pi }^{\star }(s)})-(a_{n+1}{b}_{\pi (n+1)}+\sum _{s=1}^n{a}_s{b}_{\pi (s)})\\ =& a_{n+1}\cdot (b_{n+1}-b_{\pi (n+1)})+\sum _{s=1}^n{a}_s\cdot (b_{{\pi }^{\star }(s)}-b_{\pi (s)})\\ =& a_{n+1}\cdot (b_{n+1}-b_j)+\sum _{s=1}^n{a}_s\cdot (b_{{\pi }^{\star }(s)}-b_{\pi (s)})\\ =& a_{n+1}\cdot (b_{n+1}-b_j)+a_i\cdot (b_{{\pi }^{\star }(i)}-b_{\pi (i)})+\sum _{s=1,s\ne i}^n{a}_s\cdot \stackrel{=0}{\overbrace{(b_{{\pi }^{\star }(s)}-b_{\pi (s)})}}\\ =& a_{n+1}\cdot (b_{n+1}-b_j)+a_i\cdot (b_j-b_{n+1})\\ =& (a_i-a_{n+1})\cdot (b_j-b_{n+1})\\ ⩾& 0\end{array}$

skąd natychmiast

$\begin{array}{cc}\sum _{s=1}^{n+1}{a}_s{b}_s& =a_{n+1}{b}_{n+1}+\sum _{s=1}^n{a}_s{b}_s\\ & ⩾a_{n+1}{b}_{n+1}+\sum _{s=1}^n{a}_s{b}_{{\pi }^{\star }(s)}\\ & ⩾\sum _{s=1}^{n+1}{a}_s{b}_{\pi (s)}\end{array}$

co należało dowieść.

Druga nierówność wynika z zastosowania pierwszej do ciągu $a^{\star }=(-a_{n-s+1}{)}_{s⩽n}.$