Vollständige Induktion

Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird, die größer oder gleich einem bestimmten Startwert sind. Da es sich um unendlich viele Zahlen handelt, kann eine Herleitung nicht für jede Zahl einzeln erbracht werden. Sie ist ein deduktives Verfahren.

Der Beweis, dass die Aussage ${\displaystyle \operatorname {A} (n)}$ für alle ${\displaystyle n\geq n_{0}}$ (${\displaystyle n_{0}}$ meist 1 oder 0) gilt, wird dabei in zwei Etappen durchgeführt:

1. Im Induktionsanfang wird die Gültigkeit der Aussage ${\displaystyle \operatorname {A} (n_{0})}$ für eine kleinste Zahl ${\displaystyle n_{0}}$ gezeigt.
2. Im Induktionsschritt wird für ein beliebiges ${\displaystyle n\geq n_{0}}$ die Gültigkeit der Aussage ${\displaystyle \operatorname {A} (n+1)}$ aus der Gültigkeit von ${\displaystyle \operatorname {A} (n)}$ geschlussfolgert.

Oder weniger formal formuliert:

1. Induktionsanfang: Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt.
2. Induktionsschritt: Folgendes wird bewiesen: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für deren Nachfolger.

Ausgehend vom Beweis für den Startwert erledigt der Induktionsschritt den Beweis für alle natürlichen Zahlen oberhalb des Startwertes.

Dieses Beweisverfahren ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik.