In diesem Artikel geht es um ein häufig anwendbares Beweiskonzept, die vollständige Induktion. Sie ist besonders dann gut verwendbar, wenn man eine Aussage für alle natürlichen Zahlen zeigen will. Die Idee ist, die Aussage nicht direkt zu zeigen. Stattdessen beweist man im Induktionsanfang die Aussage zunächst für ein n (normalweise n=1) und führt alle weiteren Fälle Schritt für Schritt auf diesen zurück. Dabei zeigt man im Regelfall, dass falls die Aussage für n richtig ist, sie auch für n+1 richtig sein muss. Das ist der Induktionsschritt.
Damit ist die Aussage dann für alle natürlichen Zahlen bewiesen. Für n=1 ist es direkt gezeigt. Für n=2 nutzen wir aus, dass n=1 schon gezeigt ist und wenden den Schritt an. Für n=3 nutzen wir aus, dass n=2 schon bewiesen ist und wenden wiederum den Schritt an. Man kann sich das ein bisschen wie Dominosteine vorstellen. Ein Dominostein steht für eine natürliche Zahl n. Wenn er umfällt, haben wir die Aussage für dieses n bewiesen. Unser Plan ist, zu zeigen, dass der erste Dominostein umfällt und dass der n-te Dominostein beim Umfallen den (n+1)-ten Dominostein umstößt.
Ein erstes Beispiel
Schauen wir uns ein klassisches erstes Beispiel zur vollständigen Induktion an, die Gaußsche Summenformel. Es soll die folgende Gleichung über die Summe der ersten n natürlichen Zahlen bewiesen werden:
1+2+3+\cdots+n=\frac{n(n+1)}{2}Wieso könnte vollständige Induktion hier ein guter Ansatz sein? Zunächst einmal müssen wir eine Gleichheit für alle natürlichen Zahlen beweisen. Der Induktionsanfang ist meistens nicht so schwer. Beim Induktionsschritt möchten wir die Summe der ersten n+1 natürlichen Zahlen bestimmen. Dabei dürfen wir eine Formel zur Bestimmung der Summe der ersten n natürlichen Zahlen verwenden. Schließlich setzen wir ja voraus, dass die Formel für n richtig und wollen zeigen, dass sie dann auch für n+1 gilt. Dann müssen wir also nur den letzten Summanden addieren und sind fertig!
So könnte ein Beweis mit vollständiger Induktion aussehen:
Wir beweisen die Formel mit vollständiger Induktion.
Induktionsanfang (n=1): Es gilt \frac{1\cdot 2}{2}=\frac22=1, also ist die Formel für n~=~1 richtig und der Induktionsanfang gegeben.
Induktionsschritt (n \rightarrow n+1):
Induktionsvoraussetzung: Es gilt 1+2+3+\cdots +n=\frac{n(n+1)}2\;..
Induktionsbehauptung: Es gilt 1+2+3+\cdots+n+(n+1)=\frac{(n+1)(n+1+1)}2\;.
Beweis der Induktionsbehauptung:
Es gilt
In der ersten Gleichung haben wir die Induktionsvoraussetzung verwendet. Damit ist die Induktionsbehauptung bewiesen, also der Induktionsschritt gegeben und die Induktion somit vollständig.
Aber haben wir jetzt nicht die Aussage vorausgesetzt, um die Aussage zu zeigen? Ist das nicht ein Zirkelschluss? In der Induktionsvoraussetzung steht zwar genau die gleiche Gleichung wie jene, die wir zeigen müssen. Allerdings wollen wir die Gaußsche Summenformel für alle natürlichen Zahlen zeigen. In der Induktionsvoraussetzung setzen wir die Formel immer nur für ein n voraus und zeigen dann, dass wir die Formel auch für n+1 voraussetzen können. Das ist genau die Idee der vollständigen Induktion.
Wozu der Induktionsanfang?
Was passiert, wenn der Induktionsanfang nicht gegeben ist? Kann man denn dann nicht auch schlussfolgern, dass die Aussage für alle natürlichen Zahlen gilt. Es kann doch nicht so wichtig sein, dass 1=1 gilt. Um zu demonstrieren, was dabei falsch laufen kann und wieso der Induktionsanfang wichtig ist, hier ein falscher Beweis. Wir wollen zeigen, dass Zahlen der Form 2n+1 für alle natürlichen Zahlen gerade sind. Das heißt, dass es eine ganze Zahl k gibt, sodass 2n+1=2k. Wir beweisen also im Wesentlichen, dass ungerade Zahlen gerade sind.
Beweis über Induktion (die Induktion ist nicht vollständig, weil der Anfang fehlt).
Induktionsschritt (n \rightarrow n+1):
Induktionsvoraussetzung: 2n+1 ist eine gerade Zahl.
Induktionsbehauptung: 2(n+1)+1=2n+3 ist eine gerade Zahl.
Beweis der Behauptung:
Da 2n+1 gerade ist, gibt es eine ganze Zahl k mit 2n~+~1~=~2k. Es folgt 2n+3=2k+2=2(k+1)\;. Dabei ist k+1 eine ganze Zahl, also ist 2n~+~3 tatsächlich gerade und der Induktionsschritt gegeben.
Der Induktionsschritt ist hier nicht falsch, das Problem ist eben, dass der Induktionsanfang gefehlt. Wir haben solche Aussagen gezeigt:
Wenn 3 eine gerade Zahl ist, dann ist 5 eine gerade Zahl.
Solche Aussagen kommen dir vielleicht aus dem Artikel über Logik bekannt vor. Das ist eine richtige Aussage, nur eben kein Beweis dafür, dass 5 eine gerade Zahl ist. Beim Induktionsanfang hätten wir zeigen müssen, dass 3 eine gerade Zahl ist. Das kann natürlich nicht gelingen.
Ein kombinatorisches Beispiel
Abschließend betrachten wir noch eine Aufgabe, bei dem wir nicht gerade eine Formel gegeben haben und diese nachweisen müssen. Etwas problematisch bei dem Induktionsansatz ist, dass wir wissen müssen, was herauskommt, um die Induktionsvoraussetzung zu formulieren. Bei der Gaußschen Summenformel müssen wir das Ergebnis vorher kennen oder durch ausprobieren erraten. Die vollständige Induktion liefert also nur den Beweis. Bei der folgenden Aufgabe wissen wir noch nicht, was herauskommen wird.
Wie viele Möglichkeiten gibt es ein n~\times~1~-~\text{Feld} mit Steinen der Größe 1~\times~1 und 1~\times~2 vollständig überlappungsfrei zu überdecken? Die Steine dürfen dabei nicht über den Rand hinausragen.
Die Antwort wird natürlich von n abhängen und wir müssen das für jedes n herausfinden, also könnte vollständige Induktion ein gutes Mittel sein. Wir wissen aber noch nicht, was wir beweisen müssen, also probieren wir mal etwas aus.
Für n=1 gibt es offenbar genau eine Möglichkeit, nämlich den einen 1~\times~1~-~\text{Stein} zu benutzen. Bei n=2 haben wir zwei Möglichkeiten, entweder zwei kleine Steine oder einen großen. Weiteres Probieren liefert drei Möglichkeiten für n=3 und fünf Möglichkeiten für n=4. Für n=5 findet man acht verschiedene Belegungen. Kannst du ein Muster erkennen?
Was ist eigentlich mit n=0? Je nach genauer Aufgabenstellung ist das vielleicht ausgeschlossen, aber für eine Induktion könnte das trotzdem interessant sein. Hier gibt es nur die Möglichkeit keinen Stein zu benutzen, das ist insgesamt eine Belegungsart. Schließlich ist nicht gefordert, dass man Steine benutzt. Wenn wir n=0 dazunehmen sind die ersten Anzahlen also 1, 1, 2, 3, 5 und 8. Das sind doch die Fibonaccizahlen!
Die Fibonaccifolge funktioniert so, dass wir mit zwei Einsen beginnen und dann jeweils die Summe der beiden vorherigen Glieder bilden. Sie ist definiert durch F_0~=~1, F_1~=~1 und F_n~=~F_{n-1}~+~F_{n-2}. Wir definieren A_n als die Anzahl der Möglichkeiten ein n~\times~1-Feld mit Steinen der Größe 1~\times~1 und 1~\times~2 zu belegen. Es ergibt sich die Vermutung, dass A_n=F_n gilt, also versuchen wir das über vollständige Induktion zu beweisen.
Für diese Induktion nutzen wir noch einen weiteren Trick. Es wird nicht ganz möglich sein, aus A_n=F_n auch A_{n+1}=F_{n+1} zu folgern. Schließlich hängen die Fibonaccizahlen auch von zwei Vorgängern ab. Als Induktionsvoraussetzung nutzen wir also, dass A_n=F_n und A_{n-1}=F_{n-1} gelten. Damit müssen wir die Behauptung und den Induktionanfang auch anpassen, was es aber nicht schwerer macht.
Induktionsanfang (n=1): Es ist A_1=1=F_1 und A_0=1=F_0, womit der Induktionsanfang gegeben ist.
Induktionsschritt (n \Rightarrow n+1):
Induktionsvoraussetzung: Es gilt A_n~=~F_n und A_{n-1}~=~F_{n-1}.
Indduktionsbehauptung: Es gilt A_{n+1}~=~F_{n+1} und A_{n}~=~F_{n}.
Beweis der Behauptung:
Der zweite Teil ist genauso schon in der Voraussetzung gegeben, hier ist also nichts mehr zu zeigen. Schauen wir uns das erste Feld im (n~+~1)~\times~1~\text{Feld} mal an. Das ist entweder mit einem kleinen Stein oder einem großen Stein belegt. Es bleiben also n bzw. n-1 Felder übrig. Für diese gibt es aber nach Definition A_n bzw. A_{n-1} Möglichkeiten diese Felder zu belegen. Damit sind genau die Belegungen des (n+1)\times1-Feldes betrachtet, weil jede Belegung dieses Brettes zu genau einer Belegung eines n~\times~1– bzw. (n~-~1)~\times~1~-~\text{Feldes} korrespondiert. Damit folgt
In der ersten Gleichung wird die obige Beobachtung genutzt. Die zweite Gleichung folgt aus der Induktionsvoraussetzung und die dritte Gleichung aus der Definition von Fibonaccizahlen. Damit ist der Induktionsschritt gezeigt und die Induktion vollständig.
Natürlich ist das Ergebnis jetzt nicht komplett explizit in Abhängigkeit von n. Wenn man das als geschlossene Formel haben will, könnte man noch die Formel von Moivre-Binet zur expliziten Berechnung der Fibonaccizahlen einsetzen. Diese lautet:
F_n=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right)Auch diese Formel könnte man mit vollständiger Induktion beweisen, wenn man Lust darauf hat…
Im nächsten Artikel schauen wir uns falsche Beweise an.