Die vollständige Induktion
Die vollständige Induktion ist ein Verfahren, mit dem eine Aussagefür alle natürlichen Zahlen n, die größer oder gleich einem bestimmten
Anfangswert sind, bewiesen werden soll. Das Adjektiv "vollständig"
wird in der französischen und englischen Sprache nicht verwendet,
man spricht hier vom "preuve par induction" oder "Mathematical Induction".
Die vollständige Induktion besteht aus zwei Teilen:
- dem Induktionsanfang sowie
- dem Induktionsschluss (manchmal auch Induktionsschritt genannt).
Das Prinzip ist folgendes: Wir beweisen im Induktionsschluss die in der Aufgabe
genannte Aussage für ein sogenanntes "n+1" unter der Voraussetzung, dass die Aussage
für den Vorgänger "n" richtig ist. Das genügt nicht. Es ist zusätzlich zu zeigen,
DASS die Aussage für n richtig ist. Das ist der Induktionsanfang.
Vorbemerkungen
Schauen wir einfach mal folgende Partialsummen an:
a) 1 + 3 = 4
b) 1 + 3 + 5 = 9
c) 1 + 3 + 5 + 7 = 16
d) 1 + 3 + 5 + 7 + 9 = 25
e) 1 + 3 + 5 + 7 + 9 + 11 = 36
f) 1 + 3 + 5 + 7 + 9 + 11 + 13 = 49
g) 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
h) 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81
Es ist hier so, dass wir z.B. das Ergebnis von f) in g) weiterverwenden können,
wir brauchen also nicht aufs neue 1 + 3 + 5 + 7 + 9 + 11 + 13 zu berechnen
sondern verkürzen auf 49 + 15 = 64. Und genauso von g) nach h) mit 64 + 17 = 81.
Weiterhin sehen wir, dass auf der rechten Seite die Quadratzahlen von 2*2 bis 9*9
stehen.
Und nun zu unserem ersten Beispiel, im Internet schon über 1000 mal vorgeführt,
die sogenannte "Gaußsche Summenformel".
Sie ist benannt nach dem wohl größten Mathematiker aller Zeiten Carl Friedrich Gauß
(1777-1855). Der bekam bereits als kleines Kind von seinem Lehrer die Aufgabe,
alle Zahlen von 1 bis 100 zusammenzuzählen. Also 1 + 2 + 3 + 4 + ... + 99 + 100.
Gauß änderte die Reihenfolge auf (100 + 1) + (99 + 2) + (98 + 3) + ... + (51 + 50).
In jeder Klammer steht jetzt 101, so dass er die Rechnung verkürzte und das Produkt
aus 101*50 (= 5050) berechnete.
Wenn man nur bis zur 99 aufaddieren will, dann sieht die Paarbildung etwas anders aus,
nämlich (99 + 1) + (98 + 2) ... bis zu + (51 + 49). Die alleinstehende 50 wird dann
zum Schluß addiert. Das Ergebnis ist also 100*49 + 50 = 4950.
Mit diesen Überlegungen kann man eine Gleichung aufstellen, die auf der rechten
Seite eine "Turbo-Formel" enthält, mit der sich erheblich schneller rechnen läßt:
\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~.\)
Wenn man alle Zahlen von 1 bis 200 addieren will, dann rechnet man 200*(200+1):2.
Aber ist diese Formel für alle n korrekt? Das soll im ersten von sechs Beispielen bewiesen werden.