Startseite Mathematik-Online        Themenliste


Mathematik-Online, Beweistechniken


Die vollständige Induktion lässt sich mit einer exakt aufgestellten Reihe von Dominosteinen veranschaulichen: Wenn der erste Stein umfällt und ein fallender Stein seinen Nachfolger umwirft, dann bleibt kein Stein stehen.

Vollständige Induktion

Fragestellung
Was ist das Prinzip der vollständigen Induktion?

Antwort
Damit ist folgendes Beweisverfahren gemeint:
Jeder natürlichen Zahl n ≥ m ∈ IN sei eine Aussage A(n) zugeordnet, die entweder wahr oder falsch ist. Ist A(m) wahr (Induktionsanfang) und impliziert A(n) die Aussage A(n+1), so gilt A(n) für alle n ≥ m.

Zuerst ist also zu zeigen, dass die Aussage A(m) wahr ist - meist handelt es sich bei m um die Zahl 1. Nun setzt man voraus, dass die Aussage A(n) für ein n ≥ m gilt. Hieraus wird dann im Induktionsschluss die Aussage A(n+1) abgeleitet.


Beispiel
A(n) sei die Aussage: Für alle natürlichen Zahlen n gilt 4n > n².
Für n = 1 ist die Aussage wahr, denn es gilt: 41 > 1².
Aus der Induktionsvoraussetzung 4n > n² folgt: 4⋅4n (=4n+1) > 4⋅n² ≥ n²+2n+1 = (n+1)². Damit gilt der Induktionsschluss A(n)A(n+1).

Um den Eindruck zu vermeiden, dass hierbei ein Zirkelschluss erfolgt, kann man in der Induktionsvoraussetzung die Notation k statt n verwenden. Der Induktionsschluss lautet dann A(k)A(k+1). Dies ist aber nicht nötig, wenn das Dominoprinzip (siehe oben) dem Leser bekannt ist.
Themenliste Äquivalenzrelation