Vollständige Induktion
In der Mathematik ist die Welt heil. Auf einer induktiv geordneten Menge kann man Beweise führen, die in empirischen Wissenschaften nicht klappen. Auch 999.999 beobachtete weiße Schwäne taugen nicht als Beweis, dass alle Schwäne weiß sind. Die Schwanenwelt ist nicht induktiv geordnet bzw. wissen wir nicht ob sie es ist und könnten es nicht beweisen, wenn sie es wäre. Immerhin kann man diese Vermutung widerlegen. Und tatsächlich,es gibt schwarze Schwäne. |
| Trauerschwan, Siehe Schwarzer Schwan |
Ein Beispiel? Okay, hier ist ein einfach zu zeigende Behauptung:
Die Summe der ersten $n$ ungeraden Zahlen ist $n^2$. Oder mathematisch formuliert:
\[\sum_{i=1}^n 2i-1= n^2\]
Beweis: Für $i=1$ ist $2i-1=1=1^2$. Also stimmt der Induktionsanfang. Angenommen das gelte nun auch schon bis zur Stelle \(k\ge1\), es gälte also \(\sum_{i=1}^k 2i-1= k^2\). Was passiert wenn nun die nächste ungerade Zahl dazu gezählt wird? Rechnen wir es aus:
\begin{eqnarray*}
\sum_{i=1}^{k+1} 2i-1 &=& \sum_{i=1}^k 2i-1 + 2(k+1)-1
\\ & = & k^2 + 2(k+1)-1
\\ & =& k^2 + 2k + 1
\\ & = & (k+1)^2
\end{eqnarray*}
q.e.d.
Immer nur vorwärts?
Die Induktion arbeitet prinzipiell nur vorwärts. Manchmal macht sie dabei aber Sprünge und dann müssen die Lücken gefüllt werden und man muss rückwärts argumentieren.Das arithmetische Mittel ist größer-gleich dem geometrischen Mittel
Betrachten wir dazu ein Beispiel. Das geometrische Mittel (\(\sqrt[n]{a_1^n\ldots a_n^n}\)) ist kleiner oder höchstens gleich dem arithmetischen Mittel (\(\frac1n\sum_{i=1}^n a_i\)) für alle \(a_i>0\). Diese Ungleichung sagt, dass in \(n\)-dimensionalen Würfeln die Seitenlängen kleiner sind, als bei jedem Quader mit gleichem Inhalt. Wie kann man das zeigen? Vielleicht per Induktion? Der Anfang ist ja leicht gemacht (\(n=1\)): \(\sqrt[1]{a_1}=a_1=\frac{a_1}1\)Auch für \(n=2\) kann man das auch noch relativ leicht einsehen. Mit Kenntnis der binomischen Formeln, geht das so:
\begin{eqnarray*}
(a_1-a_2)^2 & \ge & 0 & \iff
\\ a_1^2 -2a_1a_2 + a_2^2 & \ge & 0 & \iff (+4a_1a_2)
\\ a_1^2 +2a_1a_2 + a_2^2 & \ge & 4a_1a_2& \iff
\\ (a_1 + a_2)^2 & \ge & 4a_1a_2& \iff
\\ a_1 + a_2 & \ge & \sqrt{4a_1a_2} & \iff
\\ a_1 + a_2 & \ge & 2\cdot\sqrt{a_1a_2} & \iff
\\ \frac{a_1 + a_2}2 & \ge & \sqrt{a_1a_2}&
\label{eq:n2} \tag{n=2}
\end{eqnarray*}
Aber ab \(n=3\) geht das so nicht mehr. Jedenfalls nicht ganz so einfach. Trotzdem wissen wir ja nun schon etwas mehr. Den Beweis für \(n=2\) kann man ja iterieren und einen induktiven Beweis für alle \(n=2^k\) führen. Die Induktionsvoraussetzung für \(n=2=2^1\) haben wir schon gezeigt. Gelte also nun die geometrisch-arithmetische Ungleichung für ein \(2^k\), dann gilt
\begin{eqnarray*}
\frac{a_1+ \ldots + a_{2^{k+1}}}{2^{k+1}} &=& \frac{1}{2}\left(\frac{a_1+\ldots+a_{2^k}}{2^k}+\frac{a_{2^k+1}+\ldots+a_{2^{k+1}}}{2^k}\right)
\\ & \ge & \frac{1}{2}\left(\sqrt[2^k]{a_1\cdot\ldots\cdot a_{2^k}}+\sqrt[2^k]{a_{2^k+1}\cdot\ldots\cdot a_{2^{k+1}}}\right) \text{ (siehe \ref{eq:n2})}
\\ & \ge & \sqrt[2^{k+1}]{a_1\cdot\ldots\cdot a_{2^{k+1}}}
\end{eqnarray*}
Damit haben wir eine Vorwärtsinduktion über die Schrittlänge $2^k$ bewiesen. Wir wissen also nun, dass das arithmetische Mittel für $1, 2, 4, 8, 16, 32, \ldots, 2^k, \ldots$ größer ist, als das entsprechende geometrische Mittel. Es bleiben aber noch 'ne Menge Löcher zwischen diesen Abschnitten und die müssen "gefüllt" werden. Dazu bedienen wir uns der Rückwärts-Induktion! Dabei wird bewiesen, wie man von einer gültigen Aussage für den Fall $n+1$ auf den Fall $n$ schließt. Gelingt das, so heißt, dies, dass man auch weiß, dass dann die Aussage für alle $k \le n$ gilt. Schließlich kann man das Verfahren schlicht wiederholen.
Wie macht man das nun? Die Idee ist das man das Element $a_{n+1}$ so geschickt wählt, dass es sich in der Ungleichung herauskürzt. Sind also die Werte $a_1, \ldots, a_{n}$ gegeben, so wählen wir als zusätzliches $n+1$ Element genau den Mittelwert, also $\frac{a_1, \ldots, a_{n}}{n}$ der vorigen Elemente, wodurch der Mittelwert der $n+1$ Elemente dem der $n$ Elemente entspricht:
\begin{eqnarray*}
\frac{a_1 + \ldots + a_{n}+\frac{a_1+ \ldots + a_{n}}{n}}{n+1} &=& \frac{1}{n+1}\cdot\frac{n\cdot a_1 + \ldots + n\cdot a_{n}+a_1, \ldots, a_{n}}{n}
\\ & = & \frac{1}{n+1}\cdot\frac{(n+1)\cdot a_1 + \ldots + (n+1)\cdot a_{n}}{n}
\\ & = & \frac{a_1 + \ldots + a_{n}}{n}
\end{eqnarray*}
Mit anderen Worten heißt das, dass das so konstruierte arithmetische Mittel für $n+1$ dem für $n$ entspricht. Nun setzten wir wieder an
\begin{eqnarray}
\label{eq:1} \frac{a_1 + \ldots + a_{n}}{n} &=& \frac{a_1 + \ldots + a_{n}+\frac{a_1, \ldots, a_{n}}{n}}{n+1} &
\\ \label{eq:2} &\ge & \sqrt[n+1]{a_1 \cdot \ldots\cdot \frac{a_1+ \ldots + a_{n}}{n}} & \iff
\\ \label{eq:3} \left(\frac{a_1 + \ldots + a_{n}}{n}\right)^{n+1} & \ge & a_1 \cdot \ldots a_n\cdot\frac{a_1+ \ldots + a_{n}}{n} &\iff
\\ \label{eq:4} \left(\frac{a_1 + \ldots + a_{n}}{n}\right)^n & \ge & a_1 \cdot \ldots a_n&\iff
\\ \label{eq:5} \frac{a_1 + \ldots + a_{n}}{n} & \ge & \sqrt[n]{a_1 \cdot \ldots a_n}&
\end{eqnarray}
In Zeile \ref{eq:1} nutzen wir die eben gemachte Feststellung und in Zeile \ref{eq:2} die Voraussetzung, dass die Ungleichung für $n+1$ gilt. In Zeile \ref{eq:3} und \ref{eq:4} wird der zusätzlich eingeführte Term eliminiert um dann so zum Rückschluss auf den Fall $n$ der Ungleichung in Zeile \ref{eq:5} zu kommen. q.e.d.
Damit lassen sich die Lücken, die der induktive Teil des Beweises gelassen hat, durch Rückwärtsdenken füllen. Mit der Kenntnis, dass es für eine große Zahl eine Eigenschaft gilt, kann man durch geeignete Konstruktion auf die Gültigkeit der Eigenschaft für vorhergehende Zahl schließen.
