Beweisprinzip der vollständigen Induktion – Wann fallen alle Dominosteine?

Wie können wir helfen?

Du befindest dich hier:

Ein wesentlicher Pfeiler der Mathematik waren und sind die natürlichen Zahlen. Sie begegnen uns überall im Alltag, aber auch in hochabstrakten mathematischen Theorien spielen sie eine wesentliche Rolle. Allein ihre grundlegende Teilmenge der Primzahlen beispielsweise beschäftigte schon die antiken griechischen Mathematiker, aber sie fordert wegen ungelöster Fragen auch die heutigen Mathematiker noch heraus, und das nicht nur im Hinblick auf die Theorie, sondern auch für wichtige Anwendungen. 

Das Beispiel der natürlichen Zahlen weist auch auf das Grundverständnis der Mathematik hin. Zahlen und Zahlsysteme sind menschliche Erfindungen, aber ihre Verwendbarkeit und Nützlichkeit bei dem Verstehen der Welt beruht in deren Strukturen.

Die Eigenschaften der natürlichen Zahlen, dass es eine kleinste natürliche Zahl, die Eins, aber keine größte gibt, dass jede natürliche Zahl n genau einen Nachfolger n+1 besitzt, ermöglicht es in der Mathematik, Aussagen für alle natürlichen Zahlen zu machen und auch zu beweisen. Dieses Beweisprinzip nennt man “vollständige Induktion” oder auch den “Schluss von n auf n+1”. Die vollständige Induktion ist ein Prinzip oder eine Anleitung, wie man beweisen kann, dass eine Eigenschaft oder eine Behauptung sicher für alle natürlichen Zahlen gültig ist. Dabei ist dieses Beweisprinzip selbst nicht beweisbar, d.h. es hat axiomatischen Charakter. Mit dem Prinzip der vollständigen Induktion überzeugen wir uns, dass niemand je ein Gegenbeispiel finden kann, also niemand – auch in der Zukunft nicht – eine natürliche Zahl angeben kann, für die die Behauptung nicht gilt.

Hier bietet sich nun die Betrachtung eines Spieles an, dass wohl allen bekannt sein dürfte: Das systematische Aufstellen von Dominosteinen hintereinander, sodass nach dem Start alle aufgereihten Steine umfallen und keiner stehenbleibt. Hierzu gibt es ein Exponat in der Mathothek mit farbigen “Dominosteinen”, einem mit Batterie betriebenen “Aufsteller-Fahrzeug” und einem mit der Hand zu bedienenden “Starter”.

Worauf muss man nun beim Aufbau achten?

  • Erstens muss jeder nachfolgende Dominostein so gestellt werden, dass er mit Sicherheit fällt, nachdem sein Vorgänger umgefallen ist.
  • Zweitens muss der erste Stein zum Fallen gebracht werden.

Das sind auch die beiden Schritte, die unser Beweisprinzip benötigt. Streng genommen erforderte die Analogie noch ein Drittes: unendlich viele Dominosteine, z.B. eine Maschine, die ohne Ende Dominosteine so schnell aufrichtet, wie sie hinter ihr umfallen, was aber prinzipiell unmöglich und für die Anschauung auch nicht notwendig ist.

Beim Prinzip der vollständigen Induktion entspricht das “Aufsteller-Fahrzeug” dem “Induktionsschritt” und das “Startgerät” dem “Induktionsanfang” oder der “Induktionsverankerung“.

Es folgt ein Beispiel für die Anwendung des Prinzips der vollständigen Induktion. Die zu beweisende Behauptung lautet:

Für alle natürlichen Zahlen n gilt: 1+2+3+4+…+n=n⋅(n+1)/2.

I. Induktionsschritt: Aus 1+2+3+4+…+n=n⋅(n+1)/2 folgt 1+2+3+4+…+n+(n+1)=(n+1)⋅((n+1)+1), und zwar für jedes n.

Diesen Teil des Induktionsbeweises nennt man auch den Schluss von n auf n+1. Man beweist hier nicht, dass die Behauptung allgemein für n+1 gilt, sondern nur die Richtigkeit der Behauptung für n+1 unter der Voraussetzung, dass sie bereits für n richtig ist.

Beweis:

1+2+3+4+…+n=n⋅(n+1)/2 gilt wegen der Induktionsvoraussetzung.

1+2+3+4+…+n+(n+1)=n⋅(n+1)/2+(n+1) ist richtig, weil auf beiden Seiten der Gleichung (n+1) addiert wurde.

Also n⋅(n+1)/2+(n+1)= n⋅(n+1)/2+2⋅(n+1)/2 ist korrekt, weil (n+1)=2⋅(n+1)/2 gilt. Daraus ergibt sich durch das Ausklammern von (n+1)/2

n⋅(n+1)/2+2⋅(n+1)/2= (n+2)⋅(n+1)/2.

Insgesamt ergibt das durch Vergleich die Induktionsbehauptung:

1+2+3+4+…+n+(n+1)=(n+1)⋅((n+1)+1).

(Die Dominosteine sind aufgereiht! Aber wir müssen noch starten, d.h. den ersten umwerfen!)

II. Induktionsanfang:

Für n=1 ist die Behauptung wahr, denn 1=(1+1)/2 ist korrekt.

Allgemein kann man das Beweisprinzip der vollständigen Induktion so formulieren: Wenn wir beweisen wollen, dass für alle natürlichen Zahlen n eine bestimmte Aussage A(n) wahr ist, müssen wir zeigen:

  • Aus A(n) folgt immer A(n+1) für jede natürliche Zahl n. (Induktionsschritt)
  • Es gilt A(1). (Induktionsanfang oder Induktionsverankerung)

Im obigen Beispiel ist A(n) die Aussageform 1+2+3+4+…+n=n⋅(n+1)/2.

So wie es bei unserem Dominospiel garantiert ist, fällt der erste Stein, wirft der den zweiten Stein um, dieser den dritten, der wiederum den vierten usw. Kein Stein bleibt stehen, der vorherige Stein wirft ihn um. Genau so folgt aus der Gültigkeit von A(1) die Richtigkeit von A(2), aus der wiederum die Richtigkeit von A(3), die die Gültigkeit von A(4) nach sich zieht usw. Für keine natürliche Zahl k kann A(k) falsch sein, denn die Richtigkeit von A(k-1) garantiert die Gültigkeit für A(k).

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

7 − 3 =