# Tschebyscheff-Ungleichung (Arithmetik)

Die Tschebyscheff-Ungleichung (nach Pafnuti Lwowitsch Tschebyschow) ist eine Ungleichung der Mathematik.

## Aussage

Sie besagt, dass für monoton gleich geordnete n-Tupel reeller Zahlen
    $a_{1}\geq a_{2}\geq \cdots \geq a_{n}$
und
    $b_{1}\geq b_{2}\geq \cdots \geq b_{n}$,
die Beziehung
    $n\sum _{i=1}^{n}a_{i}b_{i}\geq \left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)$.
gilt. Sind $a_{i}$ und $b_{i}$ hingegen entgegengesetzt geordnet, also beispielsweise
    $a_{1}\geq a_{2}\geq \cdots \geq a_{n}$
und
    $b_{1}\leq b_{2}\leq \cdots \leq b_{n}$,
so gilt die Ungleichung in umgekehrte Richtung
    $n\sum _{i=1}^{n}a_{i}b_{i}\leq \left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)$.
Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von $a_{i}$ und $b_{i}$ notwendig sind.

## Beweise
### Beweis aus Umordnungs-Ungleichung

Die Tschebyschew-Summenungleichung lässt sich aus der Umordnungs-Ungleichung ableiten. Multipliziert man die rechte Seite aus, so ergibt sich
$\left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)=\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)$
    $+\left(a_{1}b_{2}+a_{2}b_{3}+\dots +a_{n-1}b_{n}+a_{n}b_{1}\right)$
    $+\left(a_{1}b_{3}+a_{2}b_{4}+\dots +a_{n-1}b_{1}+a_{n}b_{2}\right)$
    $+\dots$
    $+\left(a_{1}b_{n}+a_{2}b_{1}+\dots +a_{n-1}b_{n-2}+a_{n}b_{n-1}\right)$
Wegen der Umordnungs-Ungleichung ist nun jede dieser $n$ Summen (im Fall gleich geordneter Zahlen $a_{i}$ und $b_{i}$) kleiner oder gleich $\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)$, insgesamt erhält man also genau die gewünschte Beziehung
    $\left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)\leq n\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)$.
Im Fall entgegengesetzt geordneter Zahlen $a_{i}$ und $b_{i}$ braucht die Umordnungs-Ungleichung nur in die umgekehrte Richtung angewendet werden.

### Beweis mit vollständiger Induktion

Die Tschebyschew-Summenungleichung lässt sich auch mit vollständiger Induktion und Anwendung der Umordnungs-Ungleichung für den einfachsten Fall mit zwei Summanden beweisen. Der Induktionsanfang ist einfach zu führen. Im Induktionsschritt betrachtet man nun
    $\left(a_{n+1}+\sum _{i=1}^{n}a_{i}\right)\left(b_{n+1}+\sum _{i=1}^{n}b_{i}\right)=a_{n+1}b_{n+1}+\sum _{i=1}^{n}\left(a_{n+1}b_{i}+a_{i}b_{n+1}\right)+\left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)$.
Wendet man nun auf den mittleren Summanden die Umordnungs-Ungleichung für zwei Summanden und auf den letzten Summanden die Induktionsvoraussetzung an, so ergibt sich (im Fall gleich geordneter Zahlen $a_{i}$ und $b_{i}$)
    $\left(a_{n+1}+\sum _{i=1}^{n}a_{i}\right)\left(b_{n+1}+\sum _{i=1}^{n}b_{i}\right)\leq a_{n+1}b_{n+1}+\sum _{i=1}^{n}\left(a_{i}b_{i}+a_{n+1}b_{n+1}\right)+n\sum _{i=1}^{n}a_{i}b_{i}$
       $=a_{n+1}b_{n+1}+\sum _{i=1}^{n}a_{i}b_{i}+na_{n+1}b_{n+1}+n\sum _{i=1}^{n}a_{i}b_{i}=(n+1)\sum _{i=1}^{n+1}a_{i}b_{i}.$
Im Fall entgegengesetzt geordneter Zahlen $a_{i}$ und $b_{i}$ ist der Beweis analog.

### Beweis aus Gleichungs-Formulierung

Ein anderer Beweis ergibt sich direkt aus der Gleichung
    $n\sum _{i=1}^{n}a_{i}b_{i}-\left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)=\sum _{i=1}^{n}\sum _{k=i+1}^{n}(a_{i}-a_{k})(b_{i}-b_{k})={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=1}^{n}(a_{i}-a_{k})(b_{i}-b_{k})$
bzw. allgemeiner mit Gewichten $w_{i}$
    $\sum _{i=1}^{n}w_{i}\sum _{i=1}^{n}w_{i}a_{i}b_{i}-\left(\sum _{i=1}^{n}w_{i}a_{i}\right)\left(\sum _{i=1}^{n}w_{i}b_{i}\right)={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=i}^{n}w_{i}w_{k}(a_{i}-a_{k})(b_{i}-b_{k})$.
Es gilt nämlich
    $\sum _{i=1}^{n}w_{i}\sum _{k=1}^{n}w_{k}a_{k}b_{k}-\left(\sum _{i=1}^{n}w_{i}a_{i}\right)\left(\sum _{k=1}^{n}w_{k}b_{k}\right)=\sum _{i=1}^{n}\sum _{k=1}^{n}\left(w_{i}w_{k}a_{k}b_{k}-w_{i}w_{k}a_{i}b_{k}\right)$.
Mit Umbenennung der Indizes ergibt sich
    $\sum _{i=1}^{n}\sum _{k=1}^{n}\left(w_{i}w_{k}a_{k}b_{k}-w_{i}w_{k}a_{i}b_{k}\right)=\sum _{k=1}^{n}\sum _{i=1}^{n}\left(w_{i}w_{k}a_{i}b_{i}-w_{i}w_{k}a_{k}b_{i}\right)$,
insgesamt also genau die Behauptung:
    $\sum _{i=1}^{n}w_{i}\sum _{k=1}^{n}w_{k}a_{k}b_{k}-\left(\sum _{i=1}^{n}w_{i}a_{i}\right)\left(\sum _{k=1}^{n}w_{k}b_{k}\right)={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=1}^{n}w_{i}w_{k}\left(a_{k}b_{k}-a_{i}b_{k}+a_{i}b_{i}-a_{k}b_{i}\right)={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=1}^{n}w_{i}w_{k}\left(a_{i}-a_{k}\right)\left(b_{i}-b_{k}\right)$.

## Verallgemeinerung

Die Tschebyschew-Summenungleichung lässt sich auch in der Form
    ${\frac {1}{n}}\sum _{i=1}^{n}a_{i}b_{i}\geq \left({\frac {1}{n}}\sum _{i=1}^{n}a_{i}\right)\left({\frac {1}{n}}\sum _{i=1}^{n}b_{i}\right).$
schreiben. In dieser Form lässt sie sich auch auf mehr als zwei gleich geordnete n-Tupel verallgemeinern, wobei die betrachteten Zahlen allerdings größer oder gleich Null sein müssen: Für
    $a_{j}=\left(a_{j,1},\dots ,a_{j,n}\right);j=1,\dots ,m$
mit
    $a_{j,1}\geq a_{j,2}\geq \dots \geq a_{j,n}\geq 0.$
gilt
    ${\frac {1}{n}}\sum _{i=1}^{n}\prod _{j=1}^{m}a_{j,i}\geq \prod _{j=1}^{m}\left({\frac {1}{n}}\sum _{i=1}^{n}a_{j,i}\right).$
Der Beweis kann beispielsweise mit vollständiger Induktion nach $m$ erfolgen, da ja für bezüglich $i$ fallend geordnete nichtnegative Zahlen $a_{j_{i}}$ auch deren Produkte
    $\prod _{j=1}^{m}a_{j,1}\geq \prod _{j=1}^{m}a_{j,2}\geq \dots \geq \prod _{j=1}^{m}a_{j,n}\geq 0$
fallend geordnet und nichtnegativ sind.

## Varianten

Sind $f,\,g$ auf $[0,1]$ gleichsinnig monoton und ist $\omega \colon [0,1]\to \mathbb {R} _{\geq 0}$ eine Gewichtsfunktion, d. h. $\int _{0}^{1}\omega (x)dx=1$ dann ist
    $\int _{0}^{1}\omega (x)f(x)g(x)dx\geq \int _{0}^{1}\omega (x)f(x)dx\;\int _{0}^{1}\omega (x)g(x)dx$.
Zum Beweis integriert man die nichtnegative Funktion $\omega (x)\omega (y){\Bigf(x)-f(y){\Big )}{\Bigg(x)-g(y){\Big )}$ ausmultipliziert nach x und y jeweils von 0 bis 1. Dies lässt sich weiter verallgemeinern:
Sind $f_{0},\ldots ,f_{n}$ auf $[0,1]$ gleichsinnig monoton und nichtnegativ dann ist
    $\int _{0}^{1}\omega (x)\prod _{k=0}^{n}f_{k}\,dx\geq \prod _{k=0}^{n}\int _{0}^{1}\omega (x)f_{k}\,dx$.
Und sind $f_{0},...,f_{n}$ auf $[a,b]$ gleichsinnig monoton und nichtnegativ und ist $\omega \colon [a,b]\to \mathbb {R} _{\geq 0}$ eine Gewichtsfunktion dann ist
    $\int _{a}^{b}\omega (x)\prod _{k=0}^{n}f_{k}\,dx\geq {\frac {1}{(b-a)^{n-1}}}\prod _{k=0}^{n}\int _{a}^{b}\omega (x)f_{k}\,dx$.
Dies ergibt sich wenn man x durch ${\frac {x-a}{b-a}}$ substituiert.