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) \land \forall n (E (n) \to E (n + 1)) \to \forall m E (m) .$

Um die Aussage $\forall m E (m)$ zu beweisen, genügt es:

1. $E (0)$ zu zeigen (Anfangsschritt) und

2. $\forall n (E (n) \to E (n + 1))$ nachzuweisen (Induktionsschritt).

Bei der Eigenschaft 2. betrachtet man ein beliebiges $n \in 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) \to 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.