Startseite Mathematik-Online        Themenliste

Mathematik-Online

Die vollständige Induktion ist eines der wichtigsten mathematischen Beweismittel und lässt sich anhand einer regelmäßig aufgestellten Reihe von unendlich vielen Dominosteinen veranschaulichen: Wenn der erste Stein kippt (Induktionsanfang) und mit einem beliebigen Stein auch sein Nachfolger fällt (Induktionsschluss), dann stürzt die ganze Reihe um. Meist stehen die Steine für alle natürlichen Zahlen - nachfolgend aber nur für die ungeraden Zahlen:

Vollständige Induktion

Anfrage: kl, snafu
Eine Menge M von ungeraden Zahlen enthalte die Zahl 1, und mit der Zahl m liegen auch stets die Zahlen 2m - 1 und 2m + 1 in M. Wie kann ich mit Hilfe der vollständigen Induktion zeigen, dass M die Menge aller ungeraden natürlichen Zahlen ist?

Bislang kenne ich Induktionsbeweise nur für Summenformeln und weiß überhaupt nicht, wie bei diesem Problem die vollständige Induktion funktionieren soll.

Antwort:

Der Induktionsanfang (n = 1) ergibt sich direkt aus der Aufgabenstellung. Wir setzen nun voraus: Alle ungeraden Zahlen ≤ 2n-1 liegen in M. Somit ist zu zeigen: 2n+1 ∈ M.

1. Fall: Sei n gerade, also n = 2j, dann ist 2j-1 < 2n-1 ⇒ 2j+1 ≤ 2n-1. Laut Voraussetzung gilt somit: 2j+1 ∈ M. Gemäß der Aufgabenstellung liegt daher auch 2(2j+1)-1 = 2n+1 in M.

2. Fall: n = 2j-1 ⇒ 2j-1 ≤ 2n-1. Laut Voraussetzung gilt damit: 2j-1 ∈ M. Folglich liegt auch 2(2j-1)+1 = 2n+1 in M.


Mathematik-Online, vollständige Induktion


Bemerkung:

Man unterscheidet zwei Formen der vollständigen Induktion - die man übrigens von den natürlichen Zahlen auf jede wohlgeordnete abzählbare Menge leicht übertragen kann:

1) 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 folgt aus der Gültigkeit von A(n) stets die Gültigkeit von A(n+1), so gilt A(n) für alle n ≥ m.

2) Jeder natürlichen Zahl n ≥ m ∈ IN sei eine Aussage A(n) zugeordnet, die entweder wahr oder falsch ist. Ist A(m) wahr und folgt aus der Gültigkeit von A(k) mit m ≤ k ≤ n stets die Gültigkeit von A(n+1), so gilt A(n) für alle n ≥ m. (Hier setzt man also anschaulich formuliert nicht nur den n-ten Stein, sondern alle Steine von m bis n als umgefallen voraus.)
Themenliste Stufen der Unendlichkeit