Vollständige Induktion

 aufwärts

Idee

Das Beweisprinzip der Vollständigen Induktion dient dazu, Aussagen der Art

für alle n Element natürliche Zahlen gilt die Aussage A(n)

zu beweisen.

Hierzu müsste man eigentlich beweisen, dass A(1) gilt, dass A(2) gilt, dass A(3) gilt usw. Dies wäre sehr langwierig und man würde nie fertig, da die Menge natürliche Zahlen aus unendlich vielen Zahlen besteht.

Der Trick bei der Vollständigen Induktion besteht darin, dass man A(n) zunächst nur unter der Voraus­setzung zeigt, dass A(n-1) gilt. Dies bezeichnet man als den Induktions­schluss.

D.h. man beweist die Aussage

für alle n Element natürliche Zahlen mit n>1 gilt:   A(n-1)  folgt  A(n)

Das heißt, A(n) gilt, wenn A(n-1) gilt; A(n-1) gilt aber, wenn A(n-2) gilt usw. Bei A(1) bricht diese Kette ab. A(1) muss man auf andere Art beweisen; dies ist der Induktions­anfang.

Beispiel

Die Aussage A(n) sei: die Summe der Zahlen von 1 bis n ist gleich n·(n+1)/2.

Satz:  Für alle n Element natürliche Zahlen gilt:  die Summe der natürlichen Zahlen von 1 bis n beträgt  s(n) = n·(n+1)/2.

Beweis:  (Vollständige Induktion):

Induktions­anfang:   s(1) = 1·2/2 = 1,   d.h. die Behauptung gilt für n = 1.

Induktions­schluss:   Es sei n Element natürliche Zahlen, n>1 beliebig, und es gelte   s(n-1) = (n-1)·n/2.

Dann ist  s(n)  =  s(n-1) + n  =  (n-1)·n/2 + n  =  n·(n+1)/2.

Damit ist der Satz bewiesen.

Dominoprinzip

Das Prinzip der Vollständigen Induktion lässt sich durch eine Kette von umfallenden Domino­steinen ver­anschaulichen:

Alle Dominosteine fallen um, wenn folgendes sicher­gestellt ist:

  1. Dominostein 1 fällt um   und
  2. wenn Dominostein n-1 umfällt, dann fällt auch Dominostein n um  (für n>1).

Beim Aufstellen der Dominosteine muss man also aufeinander­folgende Dominosteine dicht genug aneinander stellen, damit die zweite Bedingung erfüllt ist. Und, tatsächlich fallen alle Dominosteine nur dann um, wenn der erste Stein umgeschubst wird.

 

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 04.02.2003   Updated: 13.05.2018
Valid HTML 4.01 Transitional