Einstieg in ...   Mathematik, vollständige Induktion




Die vollständige Induktion



Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage
fü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).

In unserem einführenden Beispiel werden wir die übliche Reihenfolge
absichtlich verändern, wir beginnen ausnahmsweise mit dem Induktionsschluss,
dann folgt der Induktionsanfang. Aber zunächst einige

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. Wir kommen darauf zurück.

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.