Die wichtigste Beweismethode für Aussagen über natürliche Zahlen ist die vollständige Induktion. Sie beruht auf dem
Induktionsaxiom:
Es sei E eine Eigenschaft für natürliche Zahlen n. Dann gilt
E(0)∧∀n(E(n)→E(n+1))→∀mE(m).
Um die Aussage ∀mE(m) zu beweisen, genügt es:
1. E(0) zu zeigen (Anfangsschritt) und
2. ∀n(E(n)→E(n+1)) nachzuweisen (Induktionsschritt).
Bei der Eigenschaft 2. betrachtet man ein beliebiges n∈N und zeigt:
Wenn E(n), so E(n+1).
E(n) heißt Induktionsvoraussetzung, E(n+1) Induktionsbehauptung.
Eigentlich müßte beim Induktionsschritt eine Fallunterscheidung durchgeführt werden:
Fall (a): E(n) ist falsch.
Dann ist die Implikation E(n)→E(n+1) aber trivialerweise richtig. Daher läßt man diesen Fall im Induktionsbeweis in der Regel weg und betrachtet nur noch
Fall (b): E(n) ist richtig.
Unter dieser Voraussetzung ist dann die Gültigkeit von E(n+1) zu zeigen.
Achtung: Häufig findet man bei „Anfängern“ die folgende falsche Formulierung im Induktionsschritt:
„Für beliebiges n wird vorausgesetzt, daß E(n) schon gilt.“
Wer dies so formuliert, hat die Behauptung bereits vorausgesetzt.