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).
Das Prinzip ist folgendes: Wir beweisen im Induktionsschluss die Richtigkeit einer
Aussage für ein sogenanntes "n+1" unter der Voraussetzung, dass die Aussage
für den Vorgänger "n" ebenfalls richtig ist. Das genügt aber noch nicht. Es ist zusätzlich zu zeigen,
DASS die Aussage für n richtig ist. Das ist der Induktionsanfang.
Üblicherweise wird mit dem Induktionsanfang begonnen, im ersten Beispiel wird davon abgewichen.
Vorbemerkungen
Zunächst schauen wir einfach mal folgende Summen 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 Schluss 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:
[math]\displaystyle{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~. }[/math]
Wenn man alle Zahlen von 1 bis 200 addieren will, dann rechnet man 200*(200+1):2, also 20.100 .
Aber ist diese Formel für alle n korrekt? Das soll im ersten von sechs Beispielen bewiesen werden.
Beispiel 1: Beweis der Gaußschen Summenformel
Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n [math]\displaystyle{ \geq{1} }[/math]gilt:
[math]\displaystyle{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~. }[/math]
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.
Induktionsschluss
Induktionsvoraussetzung:
Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie für jedes
beliebige n=k gelten.
[math]\displaystyle{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k \stackrel{?}{=} \frac{k*(k+1)}{2} }[/math].
Induktionsbehauptung:
Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie auch für den Nachfolger von k,
also k+1 gelten. Das nennen wir die Induktionsbehauptung.
[math]\displaystyle{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k ~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2} }[/math]
Empfehlung: Den Term "k+1" IMMER in Klammern setzen!
Jetzt holen wir die rechte Seite der Induktionsvoraussetzung und nehmen dabei an, dass diese richtig ist.
[math]\displaystyle{ \underbrace{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} ~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2} }[/math]
[math]\displaystyle{ ~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2} }[/math]
Jetzt werden beide Seiten der Gleichung umgeformt.
[math]\displaystyle{ ~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + \frac{2*(k+1)}{2}\,~ \stackrel{?}{=} \frac{(k+1)*(k+2)}{2} }[/math]
In allen Zählern die Klammern beseitigen:
[math]\displaystyle{ ~~~~~~~~~~~~~~~~~~~~\frac{k^2+k}{2}\, ~~~~~~~~~~~~~~~~~~~~~~~~~ + \frac{2k+2}{2}\,~~~~ \stackrel{?}{=} \frac{k^2+k+2k+2}{2} }[/math]
Auf beiden Seiten die Nenner entfernen und die Zähler addieren führt zu:
[math]\displaystyle{ k^2~+~3k~+2~=~k^2~+~3k~+2 }[/math]
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. Und danach der 29. 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 aber noch
zeigen, DASS ein erster Dominostein umfällt. Dieses ist unser Induktionsanfang.
Induktionsanfang
Zunächst versuchen wir, alle Dominosteine ab dem 5. zu kippen und mit n=5 erhalten wir:
[math]\displaystyle{ 1 + 2 + 3 + 4 + 5 ~ = \frac{5*(5+1)}{2}~. }[/math]
15 = 15, wahre Aussage.
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.
[math]\displaystyle{ 1 ~ = ~ \frac{1*(1+1)}{2} }[/math]
1 = 1, wahre Aussage.
Mit Hilfe von Induktionsanfang und Induktionsschluss ist jetzt gezeigt:
[math]\displaystyle{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2} }[/math]
ist gültig für alle natürlichen Zahlen n [math]\displaystyle{ \geq{1} }[/math].
Wichtig: ein Induktionsanfang ist zwingend erforderlich. Wenn dieser fehlt, ist alles andere
wertlos und der Beweis ist nicht erbracht.
Beispiel 2: Aufsummierung von Kubikzahlen
Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n [math]\displaystyle{ \geq{1} }[/math] gilt:
[math]\displaystyle{ 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ n^3 = \frac{n^2(n+1)^2}{4}~. }[/math]
Wir beginnen jetzt mit dem Induktionsanfang, wie es üblich ist. Das Fragezeichen
über dem Gleichheitszeichen lassen wir weg. Wir formen in diesem Beispiel
nur die linke Seite der Induktionsbehauptung um. Das erfordert, dass man die
Möglichkeiten des Ausklammerns und binomische Formeln erkennt.
Induktionsanfang
Wir setzen n=1:
[math]\displaystyle{ 1^3 ~ = \frac{1^2(1+1)^2}{4}\, }[/math]
1=1, wahre Aussage.
Induktionsschluss
Induktionsvoraussetzung:
[math]\displaystyle{ 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 = \frac{k^2(k+1)^2}{4}~. }[/math]
Induktionsbehauptung:
[math]\displaystyle{ 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~. }[/math]
Beweis der Induktionsbehauptung mit Anwendung der Induktionsvoraussetzung:
[math]\displaystyle{ \underbrace{1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4} }[/math]
[math]\displaystyle{ \frac{k^2(k+1)^2}{4}\, + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~. }[/math]
Wir formen hier nur die linke Gleichungsseite um.
Erweitern des zweiten Summanden (mal 4):
[math]\displaystyle{ \frac{k^2(k+1)^2}{4}\, + ~ \frac{4(k+1)^3}{4} ~ }[/math],
[math]\displaystyle{ =\frac{k^2(k+1)^2\, + ~ 4(k+1)^3}{4} ~ }[/math],
auf die rechte Seite sehen, um eine geeignete Vorgehensweise herauszufinden.
Zweckmäßig ist es, [math]\displaystyle{ (k+1)^2 }[/math] ausklammern:
[math]\displaystyle{ =\frac {(k+1)^2 [k^2+4(k+1)]}{4} ~ }[/math],
[math]\displaystyle{ =\frac {(k+1)^2 (k^2+4k+4)}{4} ~ }[/math]
Binom im zweiten Faktor erkennen:
[math]\displaystyle{ =\frac {(k+1)^2 (k+2)^2}{4} ~ }[/math],
[math]\displaystyle{ =\frac {(k+1)^2 ((k+1)+1)^2} {4} ~ }[/math]
Und das ist gleich der rechten Seite der Induktionsbehauptung.
q.e.d.
(q.e.d ist die Abkürzung für qoud erat demonstrandum, übersetzt: was zu beweisen war.
Auch ein kleines, leeres Quadrat am Ende des Beweises ist üblich.)
Eine zweite Lösungsmöglichkeit ist das Entfernen der Klammern auf beiden Seiten der IB, dann
muss man das Binom nicht erkennen. Nachteil: man kann sich leichter verrechnen.
[math]\displaystyle{ \underbrace{1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4} }[/math]
[math]\displaystyle{ \frac{k^2(k+1)^2}{4}\, + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~ }[/math]
zweiter Summand erweitert (mal 4):
[math]\displaystyle{ \frac{k^2(k+1)^2}{4}\, + ~~\frac{4(k+1)^3}{4} ~~ = \frac{(k+1)^2((k+1)+1)^2}{4}~ }[/math],
beide Seiten mal 4:
[math]\displaystyle{ k^2(k+1)^2 + 4(k^3+3k^2+3k+1)~ = ~(k+1)^2(k+2)^2 }[/math]
[math]\displaystyle{ k^2(k^2+2k+1)+4k^3+12k^2+12k+4~ = ~ (k^2+2k+1)(k^2+4k+4) }[/math]
[math]\displaystyle{ k^4+2k^3+k^2+4k^3+12k^2+12k+4 ~ = ~ k^4+2k^3+k^2+4k^3+12k^2+12k+4 }[/math]
q.e.d.
Beispiel 3: Teilbarkeiten (I)
Auch Teilbarkeiten lassen sich mit Hilfe der vollständigen Induktion beweisen.
Meistens wenden wir die Induktionsvoraussetzung erst am Ende an. Das Vorgehen ist
weitgehend gleich: wenn jeder Summand durch eine Zahl teilbar ist, dann ist auch
die gesamte Summe durch diese Zahl teilbar. Bei den Umformungen ist es Ziel, dass die
Induktionsvoraussetzung wieder zum Vorschein kommt.
Beweisen Sie: [math]\displaystyle{ 3*4^n+6 }[/math] ist für alle natürlichen Zahlen n [math]\displaystyle{ \geq{1} }[/math] durch 9 ohne Rest teilbar.
Induktionsanfang
Wir setzen n=1
[math]\displaystyle{ 3*4^1+6 = 18 }[/math], 18 ist durch 9 teilbar, wahre Aussage.
Induktionsschluss
Induktionsvoraussetzung:
[math]\displaystyle{ 3*4^k+6 }[/math] ist durch 9 teilbar.
Induktionsbehauptung:
[math]\displaystyle{ 3*4^{(k+1)} +6 }[/math] ist durch 9 teilbar.
Anwendung der Potenzgesetze führt zu:
[math]\displaystyle{ 3*4*4^k +6 }[/math]
Wir wollen erreichen, dass die IV sichtbar wird,
der Trick: wir addieren 18-18 und sortieren um.
Dieses zu erkennen ist der schwierigste Teil der Aufgabe.
[math]\displaystyle{ 3*4*4^k +6~~~ +18-18 }[/math]
[math]\displaystyle{ 3*4*4^k +24~~~ -18 }[/math]
[math]\displaystyle{ 4*(3*4^k +6)~~ -18 }[/math]
In der Klammer steht die IV, d. h. der erste Summand ist durch 9 teilbar. Auch -18 ist durch 9 teilbar.
Also ist der gesamte Ausdruck durch 9 teilbar.
q.e.d.
Beispiel 4: Teilbarkeiten (II)
Beweisen Sie, dass [math]\displaystyle{ 7^n-2^n }[/math] für alle natürlichen Zahlen n [math]\displaystyle{ \geq{1} }[/math] durch 5 ohne Rest teilbar ist.
Induktionsanfang
Wir setzen n=1
[math]\displaystyle{ 7^1-2^1 }[/math] = 5, durch 5 teilbar, wahre Aussage.
Induktionsschluss
Induktionsvoraussetzung:
[math]\displaystyle{ 7^k-2^k }[/math] ist durch 5 teilbar.
Induktionsbehauptung:
[math]\displaystyle{ 7^{(k+1)}-2^{(k+1)} }[/math] ist durch 5 teilbar.
[math]\displaystyle{ 7*7^k-2*2^k }[/math]
Ziel soll sein, die IV sichtbar machen, dazu den ersten Faktor 7 zerlegen in 5 + 2.
[math]\displaystyle{ (5+2)*7^k-2*2^k }[/math]
[math]\displaystyle{ 5*7^k+2*7^k-2*2^k }[/math]
[math]\displaystyle{ 5*7^k+2*(7^k-2^k) }[/math]
Der erste Summand ist durch 5 teilbar. Mit der IV ist auch der zweite Summand durch 5 teilbar.
Also ist der gesamte Ausdruck durch 5 teilbar.
q.e.d.
Beispiel 5: Beweis einer Ungleichung
Diesmal betrachten wir eine Ungleichung, besser wäre die Bezeichnung "Relation".
Der Umgang mit den Zeichen =, <, >, [math]\displaystyle{ \geq }[/math], [math]\displaystyle{ \leq }[/math] darf keine Schwierigkeiten machen.
Beweisen Sie: [math]\displaystyle{ 2^n \gt n^2 ~ }[/math] für alle n > 4.
Folgende Vorgehensweise ist bei Ungleichungen empfehlenswert: Man zieht die Induktionsbehauptung
auseinander und setzt die Induktionsvoraussetzung in die Mitte.
In der Abfolgekette von oben nach unten (wo die Punkte sind) dürfen nur die Zeichen
[math]\displaystyle{ =, }[/math][math]\displaystyle{ ~ \gt }[/math] und [math]\displaystyle{ \geq }[/math] auftreten. Da in der Mitte (in der Induktionsvoraussetzung) ein "[math]\displaystyle{ \gt }[/math]" steht,
würde es genügen, wenn alle anderen Zeichen ein "[math]\displaystyle{ = }[/math]" wären.
Induktionsanfang
Wir setzen [math]\displaystyle{ n=5 }[/math]
[math]\displaystyle{ 2^5 \gt 5^2 ~ \Rightarrow ~ 32\gt 25 }[/math], wahre Aussage.
Induktionsschluss
Induktionsvoraussetzung:
[math]\displaystyle{ 2^k \gt k^2 ~ }[/math]
Induktionsbehauptung:
[math]\displaystyle{ 2^{(k+1)} \gt (k+1)^2 ~ }[/math]
Beweis der Induktionsbehauptung mit Anwendung der Induktionsvoraussetzung:
[math]\displaystyle{ 2^{(k+1)} }[/math]
[math]\displaystyle{ 2^k ~ }[/math]
[math]\displaystyle{ \gt }[/math]
[math]\displaystyle{ k^2 ~ }[/math]
[math]\displaystyle{ (k+1)^2 ~ }[/math]
Zunächst sieht es gut aus. [math]\displaystyle{ 2^{(k+1)} }[/math] ist größer als [math]\displaystyle{ 2^{k} }[/math].
Aber es droht Ungemach, denn [math]\displaystyle{ k^2 ~ }[/math] ist kleiner als [math]\displaystyle{ (k+1)^2 ~ }[/math]
und es dürfen in dieser Aufgabe nur die Zeichen [math]\displaystyle{ =, }[/math][math]\displaystyle{ ~ \gt }[/math] und [math]\displaystyle{ \geq }[/math] verwendet werden.
Wir berechnen [math]\displaystyle{ 2^{(k+1)} ~ = ~ 2*2^k }[/math] und erweitern die Induktionsvoraussetzung
mit zwei. Die IV muss auf beiden Seiten erweitert werden (damit die Aussage nicht
verfälscht wird), deshalb wird [math]\displaystyle{ k^2 ~ }[/math] ebenfalls verdoppelt. Das geschieht in 2.) und 3.) .
Jetzt sieht es besser aus, es muss bewiesen werden, dass [math]\displaystyle{ 2*k^2 \geq (k+1)^2 }[/math] .
Das geschieht durch eine v.I. innerhalb einer v.I. .
Nochmal von vorne:
1.) [math]\displaystyle{ 2^{(k+1)} }[/math]
[math]\displaystyle{ = }[/math]
2.) [math]\displaystyle{ 2*2^k }[/math]
[math]\displaystyle{ \gt }[/math]
3.) [math]\displaystyle{ 2*k^2 }[/math]
[math]\displaystyle{ = }[/math]
4.) [math]\displaystyle{ k^2+k^2 }[/math]
Zu beweisen: [math]\displaystyle{ k^2 \geq {2*k+1} }[/math] für alle [math]\displaystyle{ k \geq 5 }[/math].
Induktionsanfang
4.1.) [math]\displaystyle{ n=5 }[/math]
4.2.) [math]\displaystyle{ 5^2\gt 11 }[/math], wahre Aussage.
Induktionsschluss
Induktionsvoraussetzung:
4.3.) [math]\displaystyle{ k^2 \geq {2*k+1} }[/math]
Induktionsbehauptung:
4.4.) [math]\displaystyle{ (k+1)^2 \geq {2*(k+1)+1} }[/math]
Beweis der Induktionsbehauptung:
4.5.) [math]\displaystyle{ (k+1)^2 }[/math]
[math]\displaystyle{ = }[/math]
4.6.) [math]\displaystyle{ k^2+2*k+1 }[/math]
[math]\displaystyle{ \geq }[/math]
4.7.) [math]\displaystyle{ 2*k+1 +2*k+1 }[/math]
[math]\displaystyle{ = }[/math]
4.8.) [math]\displaystyle{ 4*k+2 }[/math]
[math]\displaystyle{ \gt }[/math]
4.9.) [math]\displaystyle{ 2*k+3 }[/math]
[math]\displaystyle{ = }[/math]
4.10.) [math]\displaystyle{ 2*(k+1)+1 }[/math]
(q.e.d.)
[math]\displaystyle{ \gt }[/math]
5.) [math]\displaystyle{ k^2+2*k+1 }[/math]
[math]\displaystyle{ = }[/math]
6.) [math]\displaystyle{ (k+1)^2 }[/math]
q.e.d.