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}\geqslant a_{2}\geqslant \ldots \geqslant a_{n}$ i $b_{1}\geqslant b_{2}\geqslant \ldots \geqslant b_{n}$

lub

$a_{1}\leqslant a_{2}\leqslant \ldots \leqslant a_{n}$ i $b_{1}\leqslant b_{2}\leqslant \ldots \leqslant b_{n}.$

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

${\begin{aligned}&a_{1}b_{1}+a_{2}b_{2}+\ldots +a_{n}b_{n}\\[1ex]\geqslant {}&a_{1}b'_{1}+a_{2}b'_{2}+\ldots +a_{n}b'_{n}\\[1ex]\geqslant {}&a_{1}b_{n}+a_{2}b_{n-1}+\ldots +a_{n}b_{1}\end{aligned}}$

gdzie $(b'_{1},b'_{2},b'_{3},b'_{4},\dots ,b'_{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\leqslant n},$ $(b)_{s\leqslant 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{aligned}&\sum _{s=1}^{n}a_{s}\cdot b_{s}\\\geqslant {}&\sum _{s=1}^{n}a_{s}\cdot b_{\pi (s)}\\\geqslant {}&\sum _{s=1}^{n}a_{s}\cdot b_{n-s+1}\end{aligned}}$

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\leqslant n+1},$ $(b)_{s\leqslant 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{aligned}\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}\\&\geqslant 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{aligned}}$

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

$\pi ^{\star }(s)={\begin{cases}j&s=i\\\pi (s)&s\neq i\end{cases}}$

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

Ponadto mamy

${\begin{aligned}\sum _{s=1}^{n+1}a_{s}b_{s}&=a_{n+1}b_{n+1}+\sum _{s=1}^{n}a_{s}b_{s}\\&\geqslant a_{n+1}b_{n+1}+\sum _{s=1}^{n}a_{s}b_{\pi ^{\star }(s)}\end{aligned}}$

oraz

${\begin{aligned}&(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\neq i}^{n}a_{s}\cdot \overbrace {(b_{\pi ^{\star }(s)}-b_{\pi (s)})} ^{=\,0}\\={}&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})\\[1ex]\geqslant {}&0\end{aligned}}$

skąd natychmiast

${\begin{aligned}\sum _{s=1}^{n+1}a_{s}b_{s}&=a_{n+1}b_{n+1}+\sum _{s=1}^{n}a_{s}b_{s}\\&\geqslant a_{n+1}b_{n+1}+\sum _{s=1}^{n}a_{s}b_{\pi ^{\star }(s)}\\&\geqslant \sum _{s=1}^{n+1}a_{s}b_{\pi (s)}\end{aligned}}$

co należało dowieść.

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