Als nächstes Mathethema steht die „Vollständige Induktion“ an. Die vollständige Induktion ist ein Beweisprinzip, welches man in der Mathematik verwenden kann, um gewissen Beweise über den natürlichen Zahlen durchzuführen.

Es lässt sich mittels vollständiger Induktion leicht zeigen, dass wenn eine Aussage für ein kleinstes [latex]x_0[/latex] der natürlichen Zahlen gilt, dass dies auch für die Nachfolger des [latex]x_0[/latex] gilt.

Aufbau der vollständigen Induktion

Die Beweise werden immer nach dem gleichen Muster geführt. Das Muster besteht dabei aus vier Abschnitten, welche man sich leicht merken kann.

Induktionsanfang (I.A.)

In diesem Schritt zeigt man, dass eine Aussage für das kleinste [latex]x_0[/latex] über der natürlichen Menge gilt. Dies muss nicht immer die null sein, sondern auch andere Zahlen in [latex]\mathbb{N}[/latex], solange sie die untere Grenze darstellt.

Induktionsvoraussetzung (I.V)

Dieser Schritt besteht eigentlich im Abschreiben der zu beweisenden Aussage. Wenn wir wissen, dass die Aussage für den I.A. gilt, dann ist diese Aussage die Voraussetzung für die Nachfolger der unteren Grenze.

Induktionsbehauptung (I.B.)

Bei der Induktionsbehauptung ersetzen wir die zu beweisende Variable (oft n) durch n+1. Das soll unsere Behauptung darstellen: Die Aussage muss auch für den Nachfolger von n gelten.

Induktionsschritt (I.S.)

Der Induktionsschritt ist der rechenintensivste Schritt. Hier müssen wir zeigen, dass unter der Induktionsvoraussetzung die Induktionsbehauptung gilt. Dabei nimmt man sich die Induktionsbehauptung und formt diese nach-und-nach um, bis man die Induktionsvoraussetzung nutzen kann, um den Beweis abzuschließen.

Praxisbeispiel

Folgend werden wir eine vollständige Induktion durchführen. Dabei beweisen wir diese Behauptung: [latex]\forall x \in \{ x | x \in \mathbb{N} \wedge x \geq 3 \}. n^2 \gt 2n+1[/latex]

I.A. n=3: [latex]n^2 \gt 2n+1 \Longleftrightarrow 9 \gt 7[/latex]

Wir haben einfach die niedrigste Zahl, in dem Fall die 3, in die Ungleichung eingesetzt. Diese ist wahr, sodass wir weitermachen können.

I.V. [latex]n^2 \gt 2n+1[/latex]

Wir schreiben unsere Voraussetzung auf.

I.B. [latex](n+1)^2 \gt 2(n+1)+1[/latex]

Wir behaupten, dass die Aussage auch für das nächst größere n gelten muss.

I.S. [latex](n+1)^2 =n^2 + 2n +1 \stackrel{I.V.}{\gt} 2n+1 + 2n+1 = 4n+2\gt 2n+3 =2(n+1)+1[/latex]

Wir lösen zunächst die linke Seite auf, nutzen danach unsere Induktionsvoraussetzung, um [latex]n^2[/latex] durch [latex]2n+1[/latex] zu ersetzen. Daraus ergibt sich dann [latex]4n+2[/latex], was echt größer als die rechte Seite ist.

Alle Induktionsbeweise folgen diesem Schema im Induktionsschluss. Man formt einen Teil solange um, bis man die Voraussetzung nutzen kann, um zum Ergebnis zu gelangen.

Fazit

Man kann viele Aussagen bzw. Eigenschaften mit Hilfe der vollständigen Induktion beweisen.

~Sebastian