In der Mathematik benutzt man häufig das Beweisprinzip der vollständigen Induktion (kurz Induktionsprinzip) um die Gültigkeit einer Aussage A(n) für alle natürlichen Zahlen n zu belegen.
Dieses Beweisprinzip besteht im Wesentlichen aus zwei Teilen – dem Induktionsanfang und dem Induktionsschritt.
Mit dem Induktionsanfang n=1 hat man zu zeigen, dass die Aussage für n=1 richtig ist.
Anschließend hat man mit dem Induktionsschritt von n auf n+1 zu zeigen, dass aus der Gültigkeit der Aussage A(n) für ein beliebiges n die Gültigkeit der Aussage A(n+1) folgt. Dabei benutzt man die sogenannte Induktionsannahme oder Induktionsvoraussetzung, d.h. man nimmt für beliebiges n an, dass die Aussage A(n) richtig ist.
Gelingen beide Teile – Induktionsanfang und Induktionsschritt (unter Verwendung der Induktionsannahme), so gilt die Aussage A(n) für alle n als richtig.
Wir demonstrieren das Beweisverfahren der vollständigen Induktion an einem Beispiel:
Ein Blick auf die folgenden einfachen Rechnungen
2 = 1·2
2 + 4 = 6 = 2·3
2 + 4 + 6 = 12 = 3·4
lässt uns die folgende Vermutung äußern:
Für alle natürlichen Zahlen n ≥ 1 gilt: 2·1 + 2·2 + … + 2·n = n·(n + 1).
Beweis durch vollständige Induktion:
Induktionsanfang n = 1
2·1 = 2 = 1·2
Induktionsannahme
Für ein beliebiges n gelte 2·1 + 2·2 + … + 2·n = n·(n + 1).
Induktionsschritt von n auf n+1
Wir müssen zeigen:
Aus 2·1 + 2·2 + … + 2·n = n·(n + 1)
folgt 2·1 + 2·2 + … + 2·n + 2·(n + 1) = (n + 1)·(n + 2).
Nachweis:
| 2·1 + 2·2 + … + 2·n + 2·(n + 1) | |
| = | n·(n + 1) + 2·(n + 1) |
| = | (n + 1)·(n + 2) |
Damit gilt nach dem Induktionsprinzip unsere Vermutung als bewiesen ◊