Einstieg in ...   Mathematik, vollständige Induktion




1. Beispiel

Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n \( \geq{1} \) gilt:

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~.\)

Wir fangen (ausnahmsweise) mit dem Induktionsschluss an. Wir schreiben zuerst die sogenannte
Induktionsvoraussetzung (manchmal auch Induktionsannahme genannt) auf. Das ist nichts anderes,
als ein Abschreiben der Aufgabe. Wir benennen hier das "n" um in "k", um zu zeigen, dass
die Aussage für eine beliebige Zahl gelten soll und (noch) nicht für alle Zahlen. Viele Autoren
verzichten auf die Umbuchstabierung. Außerdem setzen wir ein Fragezeichen über das Gleichheitszeichen.


Induktionsschluss

- Induktionsvoraussetzung:

Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie auch für ein
beliebiges n=k gelten.

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k \stackrel{?}{=} \frac{k*(k+1)}{2}\) .

- Induktionsbehauptung:

Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie auch für den Nachfolger
k+1 gelten. Das nennen wir die Induktionsbehauptung. Empfehlung: IMMER k+1 in Klammern setzen!

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k ~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}\)

Die Anwendung der Induktionsvoraussetzung führt zu Folgendem:

\(\underbrace{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} ~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}\)

\(~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}\)

Jetzt werden beide Seiten der Gleichung umgeformt, links wird erweitert, rechts Klammern aufgelöst:

\(~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + \frac{2*(k+1)}{2}\,~ \stackrel{?}{=} \frac{(k+1)*(k+2)}{2}\)

In allen Zählern die Klammern beseitigen:

\(~~~~~~~~~~~~~~~~~~~~\frac{k^2+k}{2}\, ~~~~~~~~~~~~~~~~~~~~~~~~~ + \frac{2k+2}{2}\,~~~~ \stackrel{?}{=} \frac{k^2+k+2k+2}{2}\)

Auf beiden Seiten den Nenner entfernen und die Zähler optimieren führt zu:

\(k^2~+~3k~+2~=~k^2~+~3k~+2 \)

Die Induktionsbehauptung ist bewiesen, Bedingung ist die Richtigkeit der Induktionsvoraussetzung.
Wir sind daher noch nicht fertig. Jetzt ist eine Dominosteinkette aufgestellt, die Steine stehen
senkrecht und dicht genug nebeneinander. Wir wissen bis jetzt: Wenn der 27. Stein umfällt, dann fällt
auch der nachfolgende 28. Stein um. Wenn der 142.367. Stein umfällt, dann fällt auch der 142.368.
Stein um. Und wenn der erste Stein umfällt, dann fällt auch der zweite Stein um. Wir müssen
zeigen, DASS ein erster Dominostein umfällt. Das ist unser Induktionsanfang.


Induktionsanfang

Zunächst versuchen wir, den 5. Dominostein zu kippen und mit n=5 erhalten wir:

\(1 + 2 + 3 + 4 + 5 ~ = \frac{5*(5+1)}{2}~.\)

Das ergibt auf beiden Seiten fünfzehn. Der 5. Dominostein ist gefallen und alle nachfolgenden
ebenfalls. Die Aussage ist bewiesen für alle n größer oder gleich fünf. Die Aufgabe verlangte
jedoch die Untersuchung für alle n größer oder gleich eins. Also setzen wir n=1 ein.

\(1 ~ = ~ \frac{1*(1+1)}{2}\)

1 = 1, wahre Aussage.

Mit Hilfe von Induktionsanfang und Induktionsschluss ist jetzt gezeigt:

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}\)

ist gültig für alle natürlichen Zahlen n.


Wichtig: ein Induktionsanfang ist zwingend erforderlich. Wenn dieser fehlt, ist alles andere
wertlos und der Beweis ist nicht erbracht.