Chr.Nelius: Lineare Algebra (SS 2008) 1

Beweis durch vollständige Induktion

Mit Hilfe vollständiger Induktion läßt sich häufig beweisen, daß eine Aussage oder Formel für alle natürlichen Zahlen richtig ist.

n_{0} ∈ IN_{0} sei eine feste Zahl, und es sei A(n) eine Aussage in Abhängigkeit von n ∈ IN_{0}. Kann man dann beweisen:

i) A(n_{0}) ist richtig,

ii) aus der Richtigkeit von A(n) für eine beliebige, aber feste natürliche Zahl n ≥ n_{0} folgt die Richtigkeit von A(n + 1),

so ist A(n) für alle natürlichen Zahlen n ≥ n_{0} richtig.

Bezeichnungen: Ein Induktionsbeweis besteht immer aus zwei Beweis–Teilen:

1) dem Induktionsanfang (IA)

hier wird bewiesen, daß die Behauptung für n = n_{0} richtig ist (häufig ist n_{0} = 1 , aber nicht immer!)

2) dem Induktionsschluß (IS) oder dem “Schluß von n auf n + 1“:

hier wird unter der Induktionsvoraussetzung (IV), daß die Behauptung für eine beliebige (aber feste) natürliche Zahl n ≥ n_{0} richtig ist, die Induktionsbehauptung (IB) bewiesen, daß dann die Behauptung auch für n + 1 richtig ist.

Grundlage für diese Beweismethode ist das sog. Induktionsprinzip aus den Peano–Axiomen für die natürlichen Zahlen (Giuseppe Peano, 1858–1932):