Beweisverfahren, der vollständigen Induktion

Das Verfahren der vollständigen Induktion hängt eng zusammen mit der Menge der natürlichen Zahlen bzw. mit Teilmengen natürlicher Zahlen. Es ist immer dann anwendbar, wenn man auf Aussagen trifft, die für alle natürlichen Zahlen gelten, also die die folgende Struktur aufweisen:

• Für alle natürlichen Zahlen gilt .

Das Verfahren beruht auf der sogenannten Induktionseigenschaft der natürlichen Zahlen. Diese ist Bestandteil des peanoschen Axiomensystems und lautet:

• Ist T eine Teilmenge von und gilt
  
  dann ist .

Es sei die Menge aller natürlichen Zahlen, für die eine Aussage wahr ist.
Anwenden der Induktionseigenschaft besagt dann das Folgende.
Wenn man zeigen kann

dann gilt (aufgrund der als Axiom angenommenen Induktionseigenschaft) , was wiederum bedeutet ist für alle gültig.

Um die Allgemeingültigkeit einer Aussage über nachzuweisen, hat man also beim Beweis durch vollständige Induktion zwei Schritte zu vollziehen:

• Induktionsanfang
  Man zeigt, dass wahr ist.
• Induktionsschritt
  Man zeigt, dass für alle gilt: Aus der Annahme, sei richtig, kann auf die Gültigkeit von geschlossen werden, d.h.:
  
  (Inhalt des Induktionsschrittes ist also eine Implikation . Das Vorderglied heißt Induktionsvoraussetzung und das Hinterglied dieser Implikation ist die Induktionsbehauptung.)

Wichtig ist, dass beide Schritte verifiziert werden müssen, d.h. als wahr nachzuweisen sind:
sowohl der Induktionsanfang (es muss erst einmal eine natürliche Zahl geben, für die gilt)
als auch der Induktionsschritt oder Induktionsschluss (Nachweis der obigen Implikation).
Erst dann gilt, dass für alle wahr ist.

Die Struktur des Beweises durch vollständige Induktion sieht formal also folgendermaßen aus:

• Beispiel 1
  Man beweise durch vollständige Induktion:
  

• Induktionsanfang
  
• Induktionsschritt
  Induktionsvoraussetzung (n = k):
  Es gelte .
  Induktionsbehauptung (n = k + 1):
  Es sei .
  Induktionsbeweis:
  

• Beispiel 2
  Man beweise: Für alle gilt .

• Induktionsanfang
  

• Induktionsschritt
  Induktionsvoraussetzung (n = k):
  Es gelte .
  Induktionsbehauptung (n = k + 1):
  Es sei auch .
  Induktionsbeweis:
  
  Folglich gilt .