Beispiel 1:
Beweis der Gaußschen Summenformel
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. Dann folgt die Induktionsbehauptung; diese soll für das um eins
vergrößerte n gelten. Die Umbenennung von "n" in "k" erfolgt, 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. Vorübergehend setzen wir ein Fragezeichen über das Gleichheitszeichen.
Teil 2: 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.
\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k ~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}\)
Empfehlung: Das "k+1" IMMER in Klammern setzen!
Jetzt holen wir die rechte Seite der Induktionsvoraussetzung unter der Annahme, dass diese richtig ist.
\(\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.
\(~~~~~~~~~~~~~~~~~~~\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 die Nenner entfernen und die Zähler addieren 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. Zunächst ist nur 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.
Teil 1: 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 \( \geq{1} \).
Wichtig: ein Induktionsanfang ist zwingend erforderlich. Wenn dieser fehlt, ist alles andere
wertlos und der Beweis ist nicht erbracht.