Formelsammlung Mathe

Vollständige Induktion

Die vollständige Induktion ist ein Beweisverfahren, das beim Beweisen von Aussagen im Zahlenraum der natürlichen Zahlen eine wichtige Rolle spielt. Beweise per vollständiger Induktion werden immer in zwei Schritten vollzogen: Zum einen wird bewiesen, dass eine Aussage für eine kleine natürliche Zahl n0 gilt (üblicherweise ist n0 = 1). Zum andern wird gezeigt, dass die Aussage falls sie für ein beliebiges n gilt auch für n + 1 gilt. Daraus kann geschlossen werden, dass sie für jedes n > n0 gilt.

In der vollständigen Induktion beweisen wir also, dass eine Aussage für 1 gilt und dass sie, falls sie für eine Zahl gilt, auch für ihren Nachfolger gilt. Weil die Aussage für 1 gilt, gilt sie also auch für 2. Weil sie für 2 gilt, gilt sie auch für 3. Weil sie für 3 gilt, auch für 4… Da wir theoretisch in dieser Weise immer weiter machen können, schließen wir, dass die Aussage für jede natürliche Zahl gilt, egal wie groß sie auch sein mag.

Bildhaft kann man sich die vollständige Induktion wie eine Reihe von Dominosteinen vorstellen, die alle nacheinander umfallen: Wir schubsen den ersten Stein um (die Behauptung: „Der erste Stein fällt um“, ist damit wahr). Wir wissen, wenn ein Stein umfällt, stößt er auch seinen Nachbarn um (wenn die Annahme: „Der n-te Stein fällt um“, stimmt, folgt: „Der „n + 1“-te Stein fällt um“). Daraus können wir schließen, dass irgendwann jeder einzelne Dominostein umfällt.

Induktionsbeginn, Induktionsannahme und Induktionsschritt

Die Begriffe Induktionsbeginn, Induktionsannahme und Induktionsschritt bezeichnen die einzelnen Teile eines Beweises per vollständiger Induktion. Wenn wir einen Beweis per vollständiger Induktion ausführen, darf keiner dieser Teile fehlen:

Beispiel für die vollständige Induktion

Die vollständige Induktion wird gerne genutzt um Aussagen über Reihen und Folgen zu beweisen. Als Beispiel wollen wir folgende Aussage beweisen:

Die Summe aller ungeraden Zahlen kleiner 2*n ist gleich n zum Quadrat

In Worten: „Die Summe aller ungeraden Zahlen kleiner 2*n ist gleich n zum Quadrat“. Diese Aussage stimmt beispielsweise für alle ungeraden Zahlen kleiner 8 (n=4 und n2=16):

Die Summe aller ungeraden Zahlen kleiner 8 ist gleich 4 zum Quadrat also 16

Für den Induktionsbeginn zeigen wir zunächst, dass die Aussage für n0 = 1 gilt. Dies ist trivial:

Induktionsbeginn

Jetzt nehmen wir an, dass unsere Behauptung für ein beliebiges n gilt. Dies ist unsere Induktionsannahme. Unter dieser Annahme versuchen wir zu zeigen, dass sie auch für n + 1 gilt (Induktionsschritt):

Induktionsschritt

Der Induktionsschritt ist also korrekt und die Behauptung gilt für alle n > 1, d.h. für alle natürlichen Zahlen. Um die Richtigkeit des Induktionsschritt zu zeigen, haben wir in der Umformung des blau markierten Terms die Induktionsannahme genutzt.

Zusammenhang von Induktionsannahme und Induktionsbeginn

Erfahrungsgemäß bereitet es Schülern manchmal Probleme, das Verhältnis von Induktionsannahme und Induktionsbeginn in der volltständigen Induktions richtig zu begreifen. Wir wollen es deshalb noch einmal im Detail betrachten. Zunächst eine wichtige Unterscheidung:

Der Induktionsbeginn ist wie im oberen Beispiel häufig trivial, weil wir für ihn einfach nur 1 in die zu beweisende Aussage einsetzen müssen. Trotzdem dürfen wir ihn nicht vernachlässigen. Fehlt er, ist auch der Induktionsschritt wertlos.

Der Induktionsschritt ist selbst dann korrekt, wenn wir mit ihm aus einer falschen Aussage auf eine andere falsche Aussage schließen. Wir könnten beispielsweise annehmen, dass für ein beliebiges n gilt, dass 2n + 5 eine gerade Zahl ist. Dann schließen wir im Induktionsschritt, dass dies auch für n + 1 gilt, weil eine gerade Zahl zu der wir 2 addieren wieder gerade ist. Damit können wir aber noch lange nicht beweisen, dass 2n + 5 für jede natürliche Zahl n gerade ist. Wir finden nämlich keine einzige konkrete Zahl n0 für die diese Aussage wahr ist.

Obwohl der Induktionsschritt korrekt ist, lässt sich diese Aussage also nicht per vollständiger Induktion beweisen, weil der Induktionsbeginn nicht gelingt. Oder um noch einmal auf das Bild der kippenden Dominosteine zurückzukommen: Alle Steine bleiben stehen, wenn nicht wenigstens ein Stein als erstes kippt.