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:

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.


Weiter