Vollständige Induktion

[image] Aussage für natürliche Zahlen

  1. Induktionsanfang:
    [image] gilt ü

  2. Induktionsannahme:
    für jedes n gilt     [image]

  3. Induktionsschritt:
    Zeige, dass aus     [image] die Aussage [image] folgt ü.

Beim Beweisschritt ergänzt man bei allen „n“ der Induktionsannahme den Summanden „+ 1“. Dann zerlegt man diese Summe (n+1) irgendwie in „n“ und „1“ und setzt anstelle des Terms mit dem „n“ die Induktionsannahme ein. Alles Weitere ist kluges Ausrechnen. Herauskommen muss die Induktionsannahme mit dem um 1 erhöhten „n“. Macht euch das an den folgenden Beispielen klar.

 

Sei [image] eine Aussageform in der freien Variablen [image].

Sei [image] (oder [image]) eine wahre Aussage (Induktionsanfang) und die Implikation [image] für alle [image] erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in [image].