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.
Frage
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).
