Vollständige Induktion – Beweisprinzip

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 ◊

Auch interessant: