Beweis zu den Trmen von Hanoi und zustzliche Beispiele zur u a
vollstndigen Induktion a 1 Trme von Hanoi u1.1 Die Zahl bentigter
Zge rekursiv bestimmen o uWir betrachten zunchst die fr 1,2,3
Scheiben bentigte Zahl von Zgen: a u o u
Man erkennt hier, dass sich bei zwei Scheiben die Zugfolge fr
die rote Scheibe zweimal wiederholt u und ein zustzlicher Zug fr
das Umlegen der grnen Scheibe bentigt wird. Bei drei Scheiben a u u
o wiederholt sich die Zugfolge fr die rote und grne Scheibe zweimal
und ein zustzlicher Zug fr u u a u die blaue Scheibe kommt hinzu.
Als Formel notiert (Z(n) := Anzahl der fr n Scheiben bentigten
Zge): u o u Z(n + 1) = 2 Z(n) + 1
1.2 Die Zahl bentigter Zge explizit bestimmen o uDie Formel Z(n
+ 1) = 2 Z(n) + 1 nennt man eine rekursive Formel, da man zur
Bestimmung der fr ein bestimmtes n bentigten Zge zunchst die Anzahl
der fr 1, 2, 3, ..., (n 1) bentigten Zge u o u a u o u bestimmen
muss. Fr groe n ist das natrlich relativ unpraktisch, man htte
lieber eine Formel, in die man das n u u a direkt einsetzt, und
dann die Anzahl der Zge heraus bekommt. Um eine solche Formel zu
nden, u kann einem die Induktion leider kein bischen helfen. Was
hier hilft, ist sich die ersten Folgenglieder einmal nher
anzuschauen: a n 1 2 3 4 5 Z(n) 1 3 7 15 31
Man sieht jetzt (zumindest auf den zweiten Blick), dass das
gerade die Zweierpotenzen um jeweils Eins reduziert sind, also kann
man begrndet vermuten, dass eine explizite Formel wie folgt ausshe:
u a Z(n) = 2n 1 Allerdings ist das bislang eine etwas vage
Vermutung: Wir haben uns gerade mal die ersten 5 Folgenglieder
angesehen, wir brauchen aber ein Argument, dass das immer stimmt
(Man erinnere sich an die beiden falschen Primzahlformeln vom
dritten Ubungsblatt)!
1.3 Beweis mit Induktion1.3.1 Kurze Fassung (Ohne Bildchen)
Induktionsanfang: (Z(1)) Ist richtig: Unsere Formel ergibt: Z(1) =
21 1 = 1 und wir bentigen auch genau einen Zug. o
Induktionsschluss: (Z(n) Z(n + 1)) Es ist zu Zeigen, dass Z(n) =
2n+1 1 gelten muss, falls die Induktionsvoraussetzung (IV) Z(n) =
2n 1 fr ein beliebiges aber festes n richtig wre. u a Benutzen
knnen wir ferner natrlich unsere rekursive Formel, also: o u Z(n +
1) = 2 Z(n) + 1 Wir setzen nun die Induktionsvoraussetzung in diese
rekursive Formel ein, das ergibt: Z(n + 1) = 2 (2n 1) +1 = 2 2n 2 +
1 = 2n+1 1(IV)
2
1.3.2 Lange Fassung (Mit Bildchen) Wem die Verwendung der
Rekursionsformel suspekt ist, der kann es sich auch so uberlegen:
Induktionsanfang: (Z(1)) Okay, hier lass ich das Bild mal weg,
notfalls auf der ersten Seite nachsehen. Man braucht einen Zug und
das sagt ja auch unsere Formel: Z(1) = 21 1 = 1. Induktionsschluss:
(Z(n) Z(n + 1)) Es ist zu Zeigen, dass1 2 3 . . . (n 1) n n+1 | | |
| | | | | | | | | | |2n+1 1 Z ge u
| | | | | | | | | | | | | |
1 2 3 . . . (n 1) n n+1
gelten muss, falls die Induktionsvoraussetzung (IV)1 2 3 . . .
(n 1) n | | | | | | | | | | | | | | | | | | 1 2 3 . . . (n 1) n
2n 1 Z ge u
| | | | | |
fr ein beliebiges aber festes n richtig wre. u a Fangen wir also
an:1 2 3 . . . (n 1) n n+1 | | | 1 Zug | | | | | | | | | | n+1 | |
| | | | | | (IV) | | | | | | | 1 2 3 . . . (n 1) n2n 1 Z ge u
| | | | | | n+1 | | | | (IV) | | |2n 1 Z ge u
| | | | | | |
| 1 2 3 . . . (n 1) n 1 2 3 . . . (n 1) n n+1 | | | | | | |
Dass der Turm jetzt auf dem mittleren Stab liegt, strt ja nicht
wirklich (Wir htten anders anfangen o a knnen, dann htte er hinten
gelegen). Jetzt noch die Zge zusammenzhlen: o a u a (2n 1) + 1 +
(2n 1) = 2 (2n 1) + 1 = 2n+1 2 + 1 = 2n+1 1
3
2 Weitere Beispiele zur Induktion2.1 Manchmal geht es ohne
genauso gutWir wollen folgende Aussage beweisen: Die Zahl n3 n ist
immer durch 6 teilbar. 2.1.1 Mit Induktion Induktionsanfang: (A(1))
Es ist 13 1 = 0 und 0 = 6 0 also 6|0. Wen das nicht uberzeugt, der
kann die Aussage auch fr n > 1 beweisen und den Induktionsanfang
u bei 2 machen: Induktionsanfang: (A(2)) Es ist 23 2 = 6 und 6 = 6
1 also 6|6. Induktionsschluss: (A(n) A(n + 1)) Wir knnen die
Aussage in eine Gleichung verwandeln, wenn wir benutzen, dass 6|a
nichts anderes o bedeutet als: Es gibt ein k N0 mit a = 6 k. Es ist
demnach zu Zeigen, dass (n + 1)3 (n + 1) = 6 k1 gelten muss, falls
die Induktionsvoraussetzung (IV) n3 n = 6 k0 fr ein beliebiges aber
festes n richtig wre. u aRandnotiz: Warum schreibe ich hier nicht k
und k + 1? Nun, weil natrlich das k1 in der Induktionsbehauptung
nicht unbedingt eins grer sein muss u o als das k0 in der
Induktionsvoraussetzung. Wichtig ist doch nur, dass beide Terme
durch 6 teilbar sind, es also irgendeine natrliche Zahl u gibt, so
dass man den Term als 6 mal diese Zahl schreiben kann. Ich htte die
Zahlen auch Hans und Franz nennen knnen (was etwas unblich wre),
die 0 und a o u a 1 haben keine weitere Bedeutung, sind blo
verschiedene Indizes um klar zu machen, dass k0 nicht gleich k1
sein muss (aber auch nicht k1 = k0 + 1 sein muss).
Legen wir also los (ich verwende hier die Variante, mit der
linken Seite der Behauptung loszurechnen und solange umzuformen,
bis die rechte herauskommt): (n + 1)3 (n + 1) = n3 + 3 n2 + 3n + 1
n 1 = (n3 n) +3 n2 + 3n=6k0 (IV)
= 6 k0 + 3 (n + n) = 6 k0 + 3 n(n + 1)=2i,iN() =6i =6k1
2
Bei (*) habe ich nur benutzt, dass von 2 aufeinanderfolgenden
Zahlen eine durch 2 teilbar sein muss, also auch ihr Produkt. Das
liefert im Ubrigen auch die Idee fr den Beweis ohne Induktion!
u
4
2.1.2 Ohne Induktion Im Beweis mit Induktion wird die Tatsache
benutzt, dass von 2 aufeinanderfolgenden Zahlen eine durch zwei
teilbar ist, wenn man n3 1 etwas umformt, kann man noch mehr
erkennen: n3 n = n n2 n = n (n2 1) = n (n 1) (n + 1) = (n 1) n (n +
1) Das sind oensichtlich 3 aufeinanderfolgende Zahlen, von denen
ganz bestimmt eine durch 2 und eine durch 3 teilbar ist (Vgl. Ubung
3, Aufgabe 1 c)). Damit ist ihr Produkt aber sicher durch 2 3 = 6
teilbar. Man sieht: Dieser Beweis ist sehr elegant und im Prinzip
auch nicht schwieriger als der mit Induktion, da man bei beiden
etwas uber aufeinanderfolgende Zahlen wissen muss.
2.2 Manchmal geht es nicht ab EinsDamit Sie auch mal einen
Induktionsbeweis gesehen haben, wo die Aussage tatschlich erst ab
einem a bestimmten n0 > 1 richtig ist beweisen wir: Ab einem
bestimmten n0 > 1 gilt fr alle n n0 : u n2 > 2n + 1 2.2.1 Das
passende n0 bestimmen Wir gucken uns ganz einfach mal die ersten
Werte an: n 1 2 3 4 5 6 Klappt also scheinbar fr alle n 3. u 2.2.2
Mit Induktion Induktionsanfang: (A(3)) Es ist 32 = 9 und 2 3 = 7
und 9 > 7. Induktionsschluss: (A(n) A(n + 1)) Es ist zu Zeigen,
dass (n + 1)2 > 2 (n + 1) + 1 gelten muss, falls die
Induktionsvoraussetzung (IV) n2 > 2 n + 1 fr ein beliebiges aber
festes n 3 richtig wre. u a Neben der Induktionsvoraussetzung drfen
wir also im Beweis benutzen, dass n 3, also n > 2. u Wir whlen
diesmal die Variante, bei der mit der gesamten Aussage A(n)
angefangen wird und a diese durch lauter wahre Schlsse in A(n + 1)
umgeformt wird: u n2 1 4 9 16 25 36 2n + 1 3 5 7 9 11 13
5
n2 > 2 n + 1 n +2n+1>2n+1+2n+1 (n + 1)2 > 2 (n + 1) + 2
n (n + 1) > 2 (n + 1) + 12 2
|+2n+1 |n > 2 2 n > 1
(1) (2) (3) (4)
Der Schluss von (3) auf (4) sollte Sie eigentlich nicht
verwirren: Wenn n schon grer als Zwei ist, o dann ist aber ganz
sicher erst 2 n grer Eins. o Wem diese Variante nicht so gut
gefllt, der kann alternativ auch mit einer Ungleichungskette a
arbeiten (Aber aufpassen, denn es darf natrlich nirgendwo in der
kette ein (2 n + 1) + 2n + 1 = 2 (n + 1) + 2 n > 2 (n + 1) +
1(IV) 2n>1
2.2.3 Ohne Induktion Funktioniert hier nicht so richtig schn,
man kann Folgendes machen: o Ich interpretiere n2 und 2 n + 1
funktional:
Hier sehe ich, dass der blaue Graph sptestens ab 3 uber dem
roten verluft. Man kann auch noch a a umformen: n2 > 2 n + 1 n2
2 n 1 > 0 und fragt dann im Prinzip, wo der Graph der
Normalparabel oberhalb von 0 verluft: a
Man muss dafr aber in jedem Fall etwas uber Normalparabeln
wissen (nmlich, dass sie ab dem u a Scheitelpunkt monoton
wachsen).
6
