Vollständige Induktion

• Induktionsbeginn, Induktionsannahme und Induktionsschritt
• Beispiel für die vollständige Induktion
• Zusammenhang von Induktionsannahme und Induktionsbeginn

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 n₀ gilt (üblicherweise ist n₀ = 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 > n₀ 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:

• Als Induktionsbeginn bezeichnen wir den Beweis der Behauptung für n₀. Dieser Beweis muss direkt geführt werden, beispielsweise, indem wir n₀ = 1 in den Term einfügen, über den wir eine Aussage machen möchten.
• Die Induktionsannahme ist die Annahme, dass unsere Behauptung für ein beliebiges n gilt. Die Annahme wurde von uns noch nicht bewiesen. Für den Induktionsschritt nehmen wir sie als wahr an.
• Mit dem Induktionsschritt zeigen wir, dass unsere Behauptung für n + 1 gilt, falls sie für n gilt.

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:

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 n²=16):

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

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):

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:

• Beim Induktionsbeginn zeigen wir für ein konkretes n₀, dass die Aussage war ist. Üblicherweise ist n₀ = 1.
• Bei der Induktionsannahme nehmen wir an, dass die Aussage, die wir beweisen wollen, für ein irgendein beliebiges n wahr ist. Ob sie tatsächlich war ist, wissen wir nicht. Ebensowenig treffen wir eine Aussage, um welche Zahl es sich bei n handelt und ob die Aussage auch für andere n gilt.

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 n₀ 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.