Start       Mathematik       Lektionen in Analysis      Crashkurs zur vollständigen Induktion

Vertiefung zur vollständige Induktion

Im Folgenden sei N = {1, 2, 3, 4, ... } die Menge der natürlichen Zahlen.
Manche Autoren rechnen die Null zu N hinzu. Im Wesentlichen ändert sich dadurch nichts.

Die vollständige Induktion ist eine Beweistechnik, um die Allgemeingültigkeit von Aussagenformen der Form A(n) (n ε N) zu beweisen.

I Der Schluss von n auf n+1

domino.gif

Beweisschema der
vollständigen Induktion

Die Formel A(n) soll bewiesen werden.
Der Beweis erfolgt in zwei Schritten
I Induktionsanfang: Prüfe, ob A(1) wahr ist.
II Induktionsschritt: Zeige: A(n) => A(n+1) (n ε N)
("Aus A(n) kann A(n+1) hergeleitet werden")


Dieses ist das übliche Beweisschema, das auf Peano zurückgeht.
Für den Mathematiker ist das Prinzip der vollständigen Induktion ein Axiom.
Mengentheoretisch ist dazu äquivalent:

Jede nicht leere Menge von natürlichen Zahlen hat ein kleinstes Element.



Wir zeigen hier: Aus diesem Axiom läßt sich das Prinzip der vollständigen Induktion mit eine Widerspruchsbeweis herleiten.

Beweis:

Sei also A(n) eine Aussage, für die gilt:
(I)  A(1) und
(II) Aus der Gültigkeit von A(n) läßt sich auch die Gültigkeit von A(n+1) (nεN) herleiten.

Sei M={nεN|A(n) ist falsch} die Menge aller natürlicher Zahlen, für die A(n) falsch ist.

Anahme M ist nicht leer. Dann besitzt M ein kleinstes Element n0.
A(n0) ist falsch, aber für alle kleinerern Werte n ist A(n) wahr. n0 ist wegen (I) größer als 1.
Für n=n0-1 ist wegen der Minimaleigenschaft A(n) wahr.
Aus der Gültigkeit von A(n) folgt aber wegen (II) auch die Gültigkeit von A(n+1)=A(n0).
Das ist ein Widerspruch und deshalb unsere Annahme, dass M eine nichtleere Menge ist falsch.
M ist also leer, was nichts anderes besagt als dass A(n) für alle nεN wahr ist.


Viele Beispiele dazu sind im Crashkurs zur vollständigen Induktion zu finden.

Im Folgenden bringen wir einige Folgerungen (Beweise siehe unten).

II Die 1. mengentheoretische Formulierung

Axiom: Jede nichtleere Teilmenge von N, die 1 und mit n auch n+1 enthält ist N.

III Die 2. mengentheoretische Formulierung

Jede nichtleere Teilmenge von N enthält ein kleinstes Element.
Man sagt auch dazu: die Ordnung von N ist eine Wohlordnung.

IV Die starke vollständige Induktion

Den letzten Satz kann man wieder zu einem Beweisschema umformulieren.

Beweisschema der
starken
vollständigen Induktion

Die Formel A(n) soll bewiesen werden.
I Induktionsanfang: Prüfe, ob A(1) wahr ist.
Induktionsschritt:
Zeige: Wenn A(k) für alle k ≤ n gilt, dann gilt auch A(n+1) (n ε N)
1
1 → 2
1,2 → 3
1,2,3 → 4
1,2,3,4 → 5
1,2,3,4,5 → 6
1,2,3,4,5,6 → 7 ...


Ich darf hier im Induktionsschritt als Induktionsvoraussetzung nicht nur A(n) vorgeben sondern A(1), A(2), ..., A(n). Der Satz ist also "stärker" als die "normale" vollständige Induktion.

Diese Form des Induktionsprinzips wird gern verwendet, um zu zeigen, dass jede natürliche Zahl eine Primfaktorenzerlegung besitzt. (Siehe: Beweis)
Ein anderes Beispiel, bei dem diese Beweismethode Gebrauch findet, ist der erweiterte Euklidische Algorithmus.

Satz: Ist t = ggT(a,b), dann gibt es ganze Zahlen u und v mit: u·a + v·b = t. Beweis

Diesen Satz kann man auf Mengen mit einer Wohlordnung übertragen. Man nennt das Beweisschema dann "transfinite Induktion".

V Die Vorwärts-Rückwärtsmethode

Manchmal kann man nicht A(n+1) direkt aus A(n) herleiten, sondern über A(2n), A(2n-1), A(2n-2),...,A(n+1).

 1
 ↓
 2
 ↓
 4→ 3
 ↓
 8→ 7→ 6→ 5
 ↓
16→ 15→ 14→ 13→ 12→ 11→ 10→ 9
 ↓
32→ 31→ 30→ 29→ 28→ 27→ 26→ → 25→ 24→ 23→ 22→ 21→ 20→ 19→ 18→ 17
 ↓
...

Die Vorwärts-Rückwärtsmethode

Die Formel A(n) soll bewiesen werden.
I Induktionsanfang: Prüfe, ob A(1) wahr ist.
Induktionsschritt:
Zeige: Aus A(n) folgt A(2n) (n ε N) und:
Aus A(n) folgt A(n-1) (n > 1)


Ein schönes Beispiel für die Anwendung ist der Beweis der Ungleichung für das geometrische und arithmetische Mittel.

Beweise

Voraussetzung: In unserem Rechenbereich N gelten die folgenden Peanoaxiome.

Gleichgültig, welches Induktionsprinzip verwendet wird, kann in einem solchen Rechenbereich eine Addition mit n' = n + 1 definiert werden (die Multiplikation benötigen wir in unseren Beweisen nicht) und eine Kleinerrelation "<" mit n < n+1 (wobei es kein k ε N gibt mit n < k < n+1).

Die folgenden zwei Beweise sind offensichtlich. Da sie den Zusammenhang zwischen Aussageformen und Mengen aufzeigen, werden sie trotzdem demonstriert.

Beweis "I (Formulierung mit Aussagen)=>II (mengentheoretische Vormulierung)":
Sei K eine Teilmenge von N mit 1 ε K und mit n ist auch n+1 ε K.

Wir zeigen mit Hilfe des Induktionsprinzips I, dass K = N ist.

Dazu betrachten wir die Aussageform A(n): n ε K.

Es gilt A(1) (da 1 ε K) und mit A(n) auch A(n+1) (da mit n ε K auch n+1 ε K ist).
Nach dem Induktionsprinzip I gilt A(n) für alle n ε N, also gilt:
Für alle n ε N ist n ε K. Somit K = N.
q.e.d.

I ist sogar gleichwertig mit II. Wir zeigen deshalb auch:
Beweis "II (mentheoretische Formulierung)=>I (Formulierung mit Aussagen)":
Sei A(n) eine Aussage, für die A(1) und mit A(n) auch A(n+1) gilt.

Definiere K = {k ε N| A(k)}.

Dann gilt 1 ε K und mit n ε K ist auch n+1 ε K.

Nach II ist K = N, also ist A(n) für alle n ε N gültig.
q.e.d.

Der folgende Beweis ist nicht trivial.
Statt A(n): "n ist nicht in K" - was man wohl zunächst versuchen würde - definiert man
A(n): Alle k ≤ n sind nicht in K (Dank an Thomas Haunhorst in de.sci.mathematik).
Bei der ersten Definition kann es passieren, dass zwar n nicht in K aber ein k < n doch in K nicht ausgeschlossen ist.

Beweis: "I (vollständige Induktion) => III (Wohlordnung von N)":
Sei K eine Teilmenge von N ohne kleinstes Element. Wir zeigen: Dann ist K die leere Menge.

Für jedes n ε N definieren wir A(n) als die Aussage: "Es gibt kein k ε K mit k ε n".

Anders formuliert bedeutet A(n): "Es gibt kein k ε K mit k in {1,2,3,...,n}" oder "K und {1,2,...,n} sind teilerfremd."

Dann gilt:

A(1). Denn gäbe es ein k ε K mit k ≤ 1, so wäre k = 1 kleinstes Element von K.

Setzen wir nun die Induktionsvoraussetzung A(n) (n ≥ 1) voraus, d.h. Es gibt kein k ε K mit k ≤ n.

Wir zeigen dann, dass auch A(n+1) gültig ist.

Nach Induktionsvorrasusetzung ist kein k ε K in der Menge {1,2,...,n}. Dann kann aber n+1 nicht in K liegen, sonst wäre es das kleinste Element von K. Also ist auch kein Element von K in {1,2,...,n+1}, d.h. es gilt auch A(n+1).

Nach dem Induktionsprinzip ist also für alle n ε N die Aussage A(n) gültig und somit kein n ε K.

Die Menge K ist die leere Menge.
q.e.d.

Auch III ist äquivalent zu II bzw. I. Wir beweisen deshalb auch:

Beweis III(Wohlordnung von N) => II (mengentheoretische Vormulierung der vollständigen Induktion)
Sei K eine Menge, die 1 und mit n auch n+1 (n ≥ 1) enthält. Wir zeigen mit Hilfe von III, dass K = N ist.

Wir betrachten L = N \ K = {k ε N| nicht n ε K} die Komplementmenge von K.

Wäre L nicht leer, dann besäße L ein kleinstes Element n0.

n0 kann nicht 1 sein, da 1 ε K, dann ist also n0 - 1 ≥ 1 und n0 - 1 ε K = N \L.

Nach Induktionsvoraussetzung ist aber mit n0-1 auch n0εK, was nicht sein kann,
da nach unserer Annahme k ε L = N \ K ist.

Also ist L leer und K = N.
q.e.d.

Beweis III (Wohnordnung von N) => IV (starke vollständige Induktion):
Sei A(n) eine Formel mit folgender Eigenschaft:
Es gilt A(1) und wenn A(k) für alle k ≥ n gilt, dann gilt auch A(n+1) (n ε N).

Wir beweisen mit Hilfe von III, dass A(n ) für alle n ε N gilt.

Setzte K = {n ε N| nicht A(n)}. Wir zeigen über einen Widerspruchsbeweis, dass K die leere Menge ist.

Nehmen wir an, K sei nicht leer. Dann besitzt nach III K ein kleinstes Element n0 ε N.
Wegen A(1) ist n0 > 1.
Für jedes n ε N mit n < n0 gilt dann A(n). Aber dann gälte auch A(n0), was einen Widerspruch ergibt.

Auch IV ist äquivalent zu III (und damit auch zu I und II).

Beweis IV (starke vollständige Induktion)=> III (Wohnordnung von N):
Sei K eine Teilmenge von N ohne kleinstes Element.
Wir zeigen mit Hilfe von IV, dass K leer ist.

Wir betrachten die Aussage A(n): nicht n ε K:

Es gilt A(1), denn sonst wäre 1 kleinstes Element von K.

Wenn A(k) für k ≤ n gilt, d.h. wenn nicht 1 ε K, nicht 2 ε K, ..., nicht n ε K,
dann ist auch n+1 kein Element von K, sonst wäre es das kleinste in K.
Folglich gilt auch A(n+1).

Nach IV gilt A(n) für alle n ε N, also nicht n ε K für alle n ε N.

Damit ist bewiesen, dass K die leere Menge ist.
q.e.d.

Beweis III (Wohnordnung von N) => V (Vorwärts-Rückwärtsmethode):
Sei A(n) eine Aussage, für die gilt: Wir zeigen mit Hilfe von III, dass A(n) für alle n ε N gilt.

Das heißt: Wir zeigen dass die Menge K = {n ε N| nicht A(n)} leer ist.

Wäre nämlich K nicht leer, dann hätte k nach III ein kleinstes Element n.
Dies ist wegen der Gültigkeit von A(1) nicht die "1".

n ist nicht gerade, da für n = 2k (k ε N, k < n) A(k) gültig wäre
(n ist ja das kleinste Element mit nicht A(n)) und damit auch A(n) = A(2k) gültig wäre,
also nicht n ε K, folgern würde.

Nehmen wir nun an: n ist ungerade, etwa n =2k-1 ( k ε N, 1 < k < n).
Aus A(k) folgt A(2k) und aus A(2k) folgt A(n) = A(2k-1), im Wiederspruch zu nicht A(n).
q.e.d.

Beispiel zu starken vollständigen Induktion.

Satz: Jede natürliche Zahl (n ≥ 2) besitzt eine Primfaktorenzerlegung.


Beweis:
Induktionsanfang: n=2 ist Primzahl
Induktionsschritt:
Sei bereits bewiesen, dass für alle k ≤ n eine Primfaktorenzerlegung existiert (n ≥ 2).
Wir müssen zeigen, dass n+1 eine Primfaktorenzerlegung besitzt.
Ist n+1 eine Primzahl, so sind wir fertig, im anderen Fall ist n=a·b (a, b ≥ 2).
Da a ≤ n und b ≤ n ist, besitzen beide eine Primfaktorenzerlegung und damit auch n+1.
q.e.d.