Vollständige Induktion
Die vollständige Induktion beruht auf der Axiomatisierung der natürlichen Zahlen nach Peano. Insbesondere durch eine Verallgemeinerung seines fünften Axioms lässt sich die vollständige Induktion herleiten. Deshalb wird dieses fünfte und letzte Axiom auch Induktionsaxiom genannt. Verallgemeinert besagt es:
Enthält die Menge X die Zahl n0 und mit jeder natürlichen Zahl n auch deren Nachfolger n', so bilden die natürlichen Zahlen eine Teilmenge von X.
Seit dem deutschen Mathematiker Richard Dedekind, ist die vollständige Induktion folgendermaßen definiert:
Um zu beweisen, dass ein Satz für alle natürlichen Zahlen n ≥ m gilt, genügt es zu zeigen, dass er für n = m gilt und dass aus der Gültigkeit des Satzes für eine Zahl n ≥ m stets seine Gültigkeit auch für die folgende Zahl n+1 folgt.
Damit ergibt sich für die volständige Induktion immer die selber Herangehensweise:
- Induktionsanfang: Für den gewählten Startwert n0 wir die Behauptung A(n0) bewiesen
- Induktionsvorraussetzung: Für einen beliebigen aber festen Wert n mit n ≥ n0 wird die Aussage A(n) als wahr angenommen
- Induktionsschritt: Unter der Induktionsvorraussetzung wir der Beweis geführt, dass die Aussage A(n+1) ebenfalls wahr ist.
Diese drei Schritte, also Induktionsanfang, Induktionsvorraussetzung und Induktionsschritt, stellen sicher, dass die Aussage auch für alle n Gültigkeit besitzt.