Mathematik

Vollständige Induktion

Idee

Das Beweisprinzip der voll­ständigen Induktion dient dazu, Aussagen der Art

für alle n ∈ ℕ gilt die Aussage A(n)

zu beweisen.

Hierzu müsstest du eigentlich beweisen, dass A(1) gilt, dass A(2) gilt, dass A(3) gilt usw. Dies wäre sehr langwierig und du würdest nie fertig, da die Menge ℕ aus unendlich vielen Zahlen besteht.

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

D.h. du beweist die Aussage

für alle n ∈ ℕ mit n > 1 gilt:   A(n-1)  ⇒  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) musst du 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 ∈ ℕ 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 ∈ ℕ, n > 1 beliebig, und es gelte   s(n-1) = (n-1)·n/2.

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

Damit ist der Satz bewiesen.

Dominoprinzip

Du kannst dir das Prinzip der voll­ständigen Induktion 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 musst du 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 du den ersten Stein umschubst.

 

Aufgaben

Aufgabe 1:  Zeige

 Summei = 1, ..., n   i    +    Summei = 1, ..., n-1   i   =   n2

 

[up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 04.02.2003   Updated: 20.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden