Niech ciągi
(
a
1
,
a
2
,
…
,
a
n
)
{\displaystyle (a_{1},a_{2},\dots ,a_{n})}
oraz
(
b
1
,
b
2
,
…
,
b
n
)
{\displaystyle (b_{1},b_{2},\dots ,b_{n})}
liczb rzeczywistych będą jednomonotoniczne , tzn. takie, że zachodzą nierówności:
a
1
⩾
a
2
⩾
…
⩾
a
n
{\displaystyle a_{1}\geqslant a_{2}\geqslant \ldots \geqslant a_{n}}
i
b
1
⩾
b
2
⩾
…
⩾
b
n
{\displaystyle b_{1}\geqslant b_{2}\geqslant \ldots \geqslant b_{n}}
lub
a
1
⩽
a
2
⩽
…
⩽
a
n
{\displaystyle a_{1}\leqslant a_{2}\leqslant \ldots \leqslant a_{n}}
i
b
1
⩽
b
2
⩽
…
⩽
b
n
.
{\displaystyle b_{1}\leqslant b_{2}\leqslant \ldots \leqslant b_{n}.}
Wówczas prawdziwe są nierówności:
a
1
b
1
+
a
2
b
2
+
…
+
a
n
b
n
⩾
a
1
b
1
′
+
a
2
b
2
′
+
…
+
a
n
b
n
′
⩾
a
1
b
n
+
a
2
b
n
−
1
+
…
+
a
n
b
1
{\displaystyle {\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
′
,
…
,
b
n
′
)
{\displaystyle (b'_{1},b'_{2},b'_{3},b'_{4},\dots ,b'_{n})}
jest dowolną permutacją ciągu
(
b
1
,
b
2
,
b
3
,
b
4
,
…
,
b
n
)
.
{\displaystyle (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.
W pierwszej kolejności sformułujmy tezę poprawniej.
Niech
(
a
)
s
⩽
n
,
{\displaystyle (a)_{s\leqslant n},}
(
b
)
s
⩽
n
{\displaystyle (b)_{s\leqslant n}}
będą ciągami o zgodnej monotoniczności długości
n
{\displaystyle n}
i niech
π
{\displaystyle \pi }
będzie permutacją na zbiorze
{
1
,
…
,
n
}
.
{\displaystyle \{1,\dots ,n\}.}
Wówczas
∑
s
=
1
n
a
s
⋅
b
s
⩾
∑
s
=
1
n
a
s
⋅
b
π
(
s
)
⩾
∑
s
=
1
n
a
s
⋅
b
n
−
s
+
1
{\displaystyle {\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
{\displaystyle n}
i niech
(
a
)
s
⩽
n
+
1
,
{\displaystyle (a)_{s\leqslant n+1},}
(
b
)
s
⩽
n
+
1
{\displaystyle (b)_{s\leqslant n+1}}
będą ciągami o zgodnej monotoniczności długości
n
+
1.
{\displaystyle n+1.}
Niech ponadto
π
{\displaystyle \pi }
będzie permutacją zbioru
{
1
,
…
,
n
+
1
}
.
{\displaystyle \{1,\dots ,n+1\}.}
Jeśli
π
(
n
+
1
)
=
n
+
1
,
{\displaystyle \pi (n+1)=n+1,}
to
π
⋆
=
π
|
{
1
,
…
,
n
}
{\displaystyle \pi ^{\star }=\pi |_{\{1,\dots ,n\}}}
jest permutacją zbioru
{
1
,
…
,
n
}
{\displaystyle \{1,\dots ,n\}}
i wówczas
∑
s
=
1
n
+
1
a
s
⋅
b
s
=
a
n
+
1
⋅
b
n
+
1
+
∑
s
=
1
n
a
s
⋅
b
s
⩾
a
n
+
1
⋅
b
n
+
1
+
∑
s
=
1
n
a
s
⋅
b
π
⋆
(
s
)
=
a
n
+
1
⋅
b
π
(
n
+
1
)
+
∑
s
=
1
n
a
s
⋅
b
π
(
s
)
=
∑
s
=
1
n
+
1
a
s
⋅
b
π
(
s
)
{\displaystyle {\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
=
π
−
1
(
n
+
1
)
,
j
=
π
(
n
+
1
)
≠
n
+
1
{\displaystyle i=\pi ^{-1}(n+1),\,j=\pi (n+1)\neq n+1}
i niech dla
s
∈
{
1
,
…
,
n
}
{\displaystyle s\in \{1,\dots ,n\}}
π
⋆
(
s
)
=
{
j
s
=
i
π
(
s
)
s
≠
i
{\displaystyle \pi ^{\star }(s)={\begin{cases}j&s=i\\\pi (s)&s\neq i\end{cases}}}
Oczywiście
π
⋆
{\displaystyle \pi ^{\star }}
jest permutacją na zbiorze
{
1
,
…
,
n
}
.
{\displaystyle \{1,\dots ,n\}.}
Ponadto mamy
∑
s
=
1
n
+
1
a
s
b
s
=
a
n
+
1
b
n
+
1
+
∑
s
=
1
n
a
s
b
s
⩾
a
n
+
1
b
n
+
1
+
∑
s
=
1
n
a
s
b
π
⋆
(
s
)
{\displaystyle {\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
(
a
n
+
1
b
n
+
1
+
∑
s
=
1
n
a
s
b
π
⋆
(
s
)
)
−
∑
s
=
1
n
+
1
a
s
b
π
(
s
)
=
(
a
n
+
1
b
n
+
1
+
∑
s
=
1
n
a
s
b
π
⋆
(
s
)
)
−
(
a
n
+
1
b
π
(
n
+
1
)
+
∑
s
=
1
n
a
s
b
π
(
s
)
)
=
a
n
+
1
⋅
(
b
n
+
1
−
b
π
(
n
+
1
)
)
+
∑
s
=
1
n
a
s
⋅
(
b
π
⋆
(
s
)
−
b
π
(
s
)
)
=
a
n
+
1
⋅
(
b
n
+
1
−
b
j
)
+
∑
s
=
1
n
a
s
⋅
(
b
π
⋆
(
s
)
−
b
π
(
s
)
)
=
a
n
+
1
⋅
(
b
n
+
1
−
b
j
)
+
a
i
⋅
(
b
π
⋆
(
i
)
−
b
π
(
i
)
)
+
∑
s
=
1
,
s
≠
i
n
a
s
⋅
(
b
π
⋆
(
s
)
−
b
π
(
s
)
)
⏞
=
0
=
a
n
+
1
⋅
(
b
n
+
1
−
b
j
)
+
a
i
⋅
(
b
j
−
b
n
+
1
)
=
(
a
i
−
a
n
+
1
)
⋅
(
b
j
−
b
n
+
1
)
⩾
0
{\displaystyle {\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
∑
s
=
1
n
+
1
a
s
b
s
=
a
n
+
1
b
n
+
1
+
∑
s
=
1
n
a
s
b
s
⩾
a
n
+
1
b
n
+
1
+
∑
s
=
1
n
a
s
b
π
⋆
(
s
)
⩾
∑
s
=
1
n
+
1
a
s
b
π
(
s
)
{\displaystyle {\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
⋆
=
(
−
a
n
−
s
+
1
)
s
⩽
n
.
{\displaystyle a^{\star }=(-a_{n-s+1})_{s\leqslant n}.}