BANEKO GmbH
Weiter

Vollständige Induktion

Die vollständige Induktion ist ein höheres Beweisverfahren der Mathematik. Es dient dazu, eine Aussage A(n), die von einem Parameter n abhängt, für alle natürlichen Zahlen nIN zu beweisen. Dabei wird der induktive Aufbau der natürlichen Zahlen benutzt. Diese besitzen folgende wichtigen Eigenschaften:

  • 0∈IN.
  • Ist nIN, so gilt auch n+1∈IN.
  • Erfüllt eine Teilmenge MIN die beiden vorherigen Eigenschaften, so gilt bereits M = IN.

Zeigt man nun, dass die Aussage A(0) erfüllt ist, und dass aus der Annahme A(n) sei erfüllt, auch die Gültigkeit von A(n+1) folgt, so erfüllt die Menge

M = { nIN | A(n) ist erfüllt } 

die beiden ersten Bedingungen, und somit muss bereits M = IN gelten. Damit wäre die Aussage A(n) für alle nIN bewiesen — durch vollständige Induktion.

  • Das Beweisen der Aussage A(0) nennt man die Induktionsverankerung oder den Induktionsanfang. Der "Beweis" besteht dabei in der Regel darin, dass man den Wahrheitswert der (logischen) Aussage A(0) direkt überprüft.
  • Das Schließen von A(n) auf A(n+1) nennt man den Induktionsschritt oder Induktionsschluss.
  • Für den Induktionsschluss nehmen wir an, dass A(n) gültig sei. Das nennen wir die Induktionsannahme.
  • Man kann natürlich den Induktionsanfang für einem Startwert n0 > 0 zeigen. Dann gilt die Aussage A(n) für alle natürlichen Zahlen nn0.

Weiter