Vollständige Induktion

Mit dieser Beweismethode werden Sätze oder Formeln bewiesen, die von natürlichen Zahlen n abhängen. Das Prinzip der vollständigen Induktion lautet:
Ist eine Aussage für eine natürliche Zahl n0 wahr, und folgt aus der Wahrheit der Aussage für eine natürliche Zahl die Wahrheit der Aussage für , dann ist die Aussage für alle natürlichen Zahlen gültig. Danach erfolgt der Beweis in folgenden Schritten:

1. Induktionsanfang:
Die Wahrheit der Aussage wird für n=n0 gezeigt. Meist kann man n0=1 wählen.
2. Induktionsannahme:
Die Aussage sei für n wahr (Voraussetzung p).
3. Induktionsbehauptung:
Die Aussage sei für n+1 wahr (Behauptung q).
4. Beweis der Implikation

Die Schritte 3. und 4. werden zusammengefaßt als Induktionschluß oder Schluß von n auf n+1 bezeichnet.

Beispiel

Es ist die Formel zu beweisen.
Die einzelnen Schritte des Induktionsbeweises sind:

  1. ist offensichtlich richtig.
  2. sei wahr für
  3. Unter der Voraussetzung von 2. ist zu zeigen:
  4. Beweis: