Anwendungen der vollständigen Induktion · Matthias Krüger AnwendungendervollständigenInduktion UniversitätRostock InstitutfürMathematik 2 Induktionsprinzipien In diesem Teil

Anwendungen der vollständigenInduktion

Matthias Krüger

20. November 2010

Inhaltsverzeichnis

1 Einführung 2

2 Induktionsprinzipien 32.1 Klassische Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Starke Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Vorwärts-Rückwärts-Induktion . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Anwendungen bei mathematischen Problemen 63.1 Ein Beispiel aus der Ungleichungstheorie . . . . . . . . . . . . . . . . . . . 63.2 Zwei Beispiele aus der Zahlentheorie . . . . . . . . . . . . . . . . . . . . . 73.3 Eine Beispiel aus der Graphentheorie . . . . . . . . . . . . . . . . . . . . . 93.4 Ein Beispiel aus der Geometrie . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Induktion bei Internationalen Mathematik-Olympiade 11

Bei Fragen und Anregungen könnt ihr euch melden unter:[email protected]

1

Matthias KrügerAnwendungen der vollständigen Induktion

Universität RostockInstitut für Mathematik

1 Einführung

Diese Ausarbeitung ist eine Zusammenfassung meines Vortrages, welchen ich im Rahmendes mathematischen Seminars bei Prof. Dr. Gronau im Sommersemester 2010 gehaltenhabe. Ziel ist es verschiedenste Anwendungen der vollständigen Induktion zu präsentie-ren. Dabei gehen wir davon aus, dass das Induktionsprinzip den Hörern (in diesem Falleeher Lesern) bekannt ist. Es wird nur knapp auf das klassische Induktionsprinzip ein-gegangen und seine Funktionsweise, die auf den Peano1-Axiomen beruhen, soll nichtweiter erläutert werden.Wir werden im ersten Teil drei wichtige Induktionsprinzipien vorstellen und jedes an

einem Beispiel näher anschauen. Danach widmen wir uns dem Hauptteil des Vortrages:Es sollen aus verschiedensten mathematischen Gebieten Probleme vorgestellt werden -in ihrer Struktur mitunter nicht allzu trivial - die mit Hilfe eines Induktionsargumentesgelöst und Sätze damit bewiesen werden können. Ausgehend davon, dass die vollstän-dige Induktion historisch gesehen seine Ursprünge in arithmetischen Problemen hatte,beschäftigen wir uns hier mit ungleichungs-, graphen- und zahlentheoretischen sowie geo-metrischen Problemen. Näheres dazu in Kapitel 3. Im Schlussteil soll eine Aufgabe derInternationalen Mathematik-Olympiade vorgestellt und mit Hilfe einer Quasi-Induktiongelöst werden. Dabei werden wir die Aufgabenstellung ein wenig umformulieren, damitdie Induktion funktioniert, dennoch bleibt die Aussage im Kern die gleiche.Da meine Vortragszeit begrenzt war, ich aber in meinen Materialen, die am Ende

aufgeführt werden, einige interessante Beispiele mehr gefunden habe als ich vorstellenkonnte, sollen diese mit in diese Ausarbeitung fallen.Viel Spaß beim Anschauen und Nachvollziehen!

1Giuseppe Peano (∗27. August 1858 in Spinetta, Piemont; †20. April 1932 in Turin) war ein italie-nischer Mathematiker. Er arbeitete in Turin und befasste sich mit mathematischer Logik, mit derAxiomatik der natürlichen Zahlen (Entwicklung der Peano-Axiome) und mit Differentialgleichungenerster Ordnung.

2



2 Induktionsprinzipien

In diesem Teil soll es darum gehen, drei wesentliche Induktionsprinzipien vorzustellenund an jeweils einem Beispiel sich die jeweilige Funktionsweise zu verdeutlichen.

2.1 Klassische Induktion

Definition 1. Sei n0 eine ganze Zahl und A(n) für jedes n ≥ n0 eine Aussage. Um A(n)für alle n ≥ n0 zu beweisen, genügt es zu zeigen:

(IA) A(n0) ist wahr (Induktionsanfang).

(IS) Für ein beliebiges n ≥ n0 gilt: Falls A(n) wahr ist, so ist auch A(n + 1) wahr(Induktionsschritt).

Das ist das Induktionsprinzip, was uns am geläufigsten ist. Wir starten bei einemn0 und mit Hilfe des Induktionsschlusses muss damit die Aussage auch für n0 + 1 warsein. Anschaulich passiert das gleiche bei einer Dominokette: Erschlage ich den erstenStein und sorge dafür, dass der Vorherige immer den Folgenden umstößt, kippt meineganze Kette und eine Aussage A ist für alle n ab n0 bewiesen. Hier wird nochmal derZusammenhang wichtig, dass wir meist eine Induktionsvariable (meist aus N) benötigen.Wir werden bei der IMO-Aufgabe sehen, dass das nicht unbedingt der Fall sein muss.Als einfaches Beispiel, was aus dem 1. Semester des Mathestudiums bekannt sein dürfte,schauen wir uns folgenden Satz an:

Satz 1. Für alle n ∈ N gilt

n∑i=1

i2 =n(n+ 1)(2n+ 1)

6.

Beweis. Mit Hilfe unseres klassischen Induktionsprinzipes bekommen wir:

(IA) Anfang mit n = 1 liefert1∑i=1

i2 = 1 =1

61(1 + 1)(2 + 1).

(IS) Schritt für n −→ n+ 1 ist

n+1∑i=1

i2 =n∑i=1

i2 + (n+ 1)2IV=

1

6n(n+ 1)(2n+ 1) + (n+ 1)2

= (n+ 1)

((n+ 1) +

1

6n(2n+ 1)

)=

1

6(2n2 + 7n+ 6)

=1

6(n+ 1)(n+ 2)(2n+ 3).

3



2.2 Starke Induktion



(IS) Falls für alle k ∈ {n0, . . . , n} die Aussage A(k) wahr ist, so ist auch A(n+1) wahr(Induktionsschritt).

Dieses Prinzip ist dahingehend um einiges stärker, da wir für den Induktionsschluss,wie oben beschrieben, alle k ∈ {n0, . . . , n} benutzen. Während wir bei der klassischenInduktion wirklich nur n als Voraussetzung benötigen, benutzen wir hier eine ganzeMenge von Zahlen die zwischen n0 und n liegen. Welche und wie viele man von diesennutzt, ist dabei unerheblich. Im Ernstfall braucht man alle, wie das folgende Beispielzeigt.

Satz 2. Jede natürliche Zahl (n ≥ 2) besitzt eine Primfaktorzerlegung.

Beweis. Wir nutzen die Starke Induktion wie folgt:

(IA) Die Zahl n = 2 ist eine Primzahl.

(IS) Sei bereits bewiesen, dass für alle 2 ≤ k ≤ n eine PFZ existiert. Sei im ersten Falln+ 1 eine Primzahl, dann sind wir fertig. Ansonsten ist

n+ 1 = ab

mit a, b ≥ 2. Da aber dann a ≤ n und b ≤ n ist, besitzen beide eine PFZ und somitauch ihr Produkt.

2.3 Vorwärts-Rückwärts-Induktion



(IS) Für ein beliebiges n ≥ n0 gilt: Falls A(n) wahr ist, so sind auch A(m) mit m ≥ n+2beliebig und A(n− 1) wahr (Induktionsschritt).

Die Funktionsweise kann man sich auch relativ gut klarmachen: Man macht durch dasm ein großen Vorwärtsschritt und zeigt die Gültigkeit von A(m). Aufgrund der Tatsache,dass man auch die Gültigkeit von A(n−1) zeigt, gilt, dass A(m−1), A(m−2), . . . , A(n+1)ebenfalls war sind. Dies kann man nun beliebig fortführen und zeigt damit die Gültigkeitvon A für alle n ≥ n0. Der folgende wichtige Satz lässt sich mit Hilfe dieses Prinzipsbeweisen.

4



Satz 3 (AM-GM-Ungleichung). Für n nichtnegative reelle Zahlen x1, . . . , xn gilt(n∏i=1

xi

) 1n

≤ 1

n

(n∑i=1

xi

).

Beweis. Wir halten zunächst fest, dass wir ohne Beschränkung der Allgemeinheit an-nehmen, dass für alle i ∈ [n] := {1, . . . , n} xi ungleich 0 ist. Denn ist eines (oder alle)der xi = 0, dann ist das Produkt auf der linken Seite gleich 0 und die rechte Seite istebenfalls gleich 0 wenn alle xi = 0 sind, oder größer als 0 wenn bereits mindestens einepositive Zahl dabei ist. Seien die xi im Folgenden also alle positiv.

(IA) Der Induktionsanfang ist für n = 1 trivial, denn dann ist x1 ≤ x1, was offensichtlichstimmt. Für den Induktionsschritt benötigen wir später noch den Fall n = 2. Fürdiesen benutzen wir binomische Formeln und äquivalentes Umformen:

(x1 − x2)2 ≥ 0⇐⇒ x21 − 2x1x2 + x22 ≥ 0⇐⇒ x21 + 2x1x2 + x22 ≥ 4x1x2

⇐⇒ (x1 + x2)2 ≥ 4x1x2 ⇐⇒ x1 + x2 ≥ 2

√x1x2

⇐⇒√x1x2 ≤

1

2(x1 + x2).

Das Wurzelziehen ist dahingehend unbedenklich da jede Seite positiv ist.

(IS) Wir machen einen Vorwärtsschritt der Form n −→ m = 2n. Dazu definieren wiruns

a =

(n∏i=1

xi

) 1n

und b =

(2n∏

i=n+1

xi

) 1n

und erhalten damit nach Induktionsanfang und -voraussetzung

(ab)12 ≤ 1

2(a+ b) sowie a ≤ 1

n

(n∑i=1

xi

)und b ≤ 1

n

(2n∑

i=n+1

xi

).

Mit diesen Ungleichungen gelten nun folgende Abschätzungen(2n∏i=1

xi

) 12n

= (ab)12 ≤ 1

2(a+ b) ≤ 1

2

(1

n

n∑i=1

xi +1

n

2n∑i=n+1

xi

)=

1

2n

2n∑i=i

xi.

Für den Rückwärtsschritt der Form n −→ n − 1 nehmen wir n − 1 positive reelleZahlen und setzen

c =

(n−1∏i=1

xi

) 1n−1

.

Dann ist

c = (cn)1n = (cn−1c)

1n =

(cn−1∏i=1

xi

) 1n

≤ 1

n

(n−1∑i=i

xi + c

)

5



und durch äquivalentes Umformen nach c schlussendlich

c− c

n≤ 1

n

n−1∑i=i

xi ⇐⇒ (n− 1)c ≤n−1∑i=i

xi ⇐⇒ c ≤ 1

n− 1

n−1∑i=i

xi.

3 Anwendungen bei mathematischen Problemen

In diesem Teil der Ausarbeitung sollen insgesamt 5 mathematische Probleme formuliertund mit Hilfe der vollständigen Induktion gelöst werden. Diese Probleme entstammenverschiedensten Teilgebieten der Mathematik und beinhalten mitunter ein Konstrukti-onsverfahren, wie wir an vereinzelten Beispielen feststellen werden. Zuerst wollen wir inder Ungleichungstheorie bleiben und ein Korollar der AM-GM-Ungleichung mit Indukti-on beweisen.

3.1 Ein Beispiel aus der Ungleichungstheorie

Satz 4. Seien x1, . . . , xn mit n ≥ 4 nichtnegative reelle Zahlen mit x1+ . . . xn = 1. Dannist

x1x2 + x2x3 + . . .+ xnx1 ≤1

4.

Beweis. Wir machen eine Induktion über n.

(IA) Den Induktionsanfang machen wir mit n = 4. Hierzu überlegen wir uns folgendeGleichheit

S4 = x1x2 + x2x3 + x3x4 + x4x1 = x1x2 + x1x4 + x3x2 + x3x4

= x1(x2 + x4) + x3(x2 + x4) = (x1 + x3)(x2 + x4).

Durch Anwendung der AM-GM-Ungleichung (Satz 3) auf die beiden nichtnegativenZahlen x1+x3 und x2+x4 gilt

√(x1 + x3)(x2 + x4) ≤ 1

2(x1+x2+x3+x4), sowieweil x1 + x2 + x3 + x4 = 1 folgt

S4 = (x1 + x3)(x2 + x4) ≤1

4(x1 + x2 + x3 + x4)

2 =1

4.

(IS) Wir machen einen Induktionsschritt der Form n−1 −→ n. Dazu seien nun nichtne-gative reelle Zahlen x1, . . . xn gegeben, die zusammen addiert den Wert 1 ergeben.Ordnet man diese Zahlen auf einem regulären n-Eck an, so ist die zu berechnendeSumme die Summe der Produkte zweier aufeinanderfolgender Ecken dieses n-Ecks.Seien nun a, b, c, d vier dieser n Zahlen, die sich hintereinander auf dem n-Eck be-finden und von denen wir fordern, dass a ≥ b erfüllt ist. Es ist klar, dass solcheZahlen immer zu finden sind. Dann gilt folgende Abschätzung:

ab+ bc+ cd ≤ ab+ ac+ cd ≤ ab+ ac+ bd+ cd = a(b+ c) + (b+ c)d

6



Fassen wir nun die Zahlen b und c zu einer Zahl b + c zusammen, so haben wirnun n− 1 nichtnegative Zahlen, deren Summe 1 ergibt. Mit der eben hergeleitetenAbschätzung folgt dann

Sn ≤ S∗n−1 ≤1

4.

Dabei beschreibt S∗n−1 eine Summe der obigen Form die durch n−1 Zahlen gebildetwird. Die Richtigkeit der Ungleichung ist für n−1 gerade durch die Induktionsvor-aussetzung gegeben und somit der Satz bewiesen.

Bemerkung. Matthias Schuchardt hat in der Woche nach mir gezeigt, dass für jedesn ∈ N mit n ≥ 3 und reellen Zahlen x1, . . . , xn, deren Summe 1 ergibt, eine Permutationπ ∈ Sn existiert, mit der

n∑i=1

xπ(i)xπ(i+1) ≤1

n

ist. Der Satz von eben zeigt also, dass bei n = 4, unter der Voraussetzung der Nichtne-gativität der xi, jede Permutation aus S4 diese Bedingung erfüllt.

3.2 Zwei Beispiele aus der Zahlentheorie

Satz 5. Jede positive ganze Zahl k ≤ n! kann als Summe von n oder weniger verschie-denen Teilern von n! dargestellt werden.

Beweis. (IA) Für n = 1 ist die Aussage wahr.

(IS) Gelte diese Aussage nun für ein n ≥ 1. Wir betrachten nun ein beliebiges k ∈ N mitk ≤ (n+1)!. Dieses k können wir darstellen als k = q(n+1)+ r mit 0 ≤ r < n+1.Daraus folgt, dass q ≤ n! ist. Für dieses q gilt nach Induktionsvoraussetzung die Be-hauptung. Es existieren also d1, . . . , dm mit m ≤ n, welches paarweise verschiedeneTeiler von n! sind. Es gilt dann

q =

m∑i=1

di = d1 + . . .+ dm.

Somit hat dann k die Darstellung

k = d1(n+ 1) + . . .+ dm(n+ 1) + r.

Die Anzahl der Summanden in der Darstellung von k ist höchstens n + 1. Fernersind die di alle verschieden nach Voraussetzung also auch dann noch wenn mansie alle mit der gleichen Zahl multipliziert, somit sind die di(n + 1) untereinanderverschieden und ≥ n + 1 sowie verschieden von r ≤ n + 1. Die Summanden sindauch alle Teiler von (n + 1)!, denn di teilt n! und folglich di(n + 1) dann auch(n+ 1)!, ebenso wie r < n+ 1. Damit ist die Behauptung bewiesen.

7



Induktion ist nicht nur ein sehr nützliches Hilfsmittel um Behauptungen zu beweisen,sondern auch zum Konstruieren mathematischer Objekte mit bestimmten Eigenschaftengeeignet. Das folgende Problem wurde in Matematika, Nr. 6, im Jahre 1981 von PlamenDzhakov publiziert:

Satz 6. Sei p eine Primzahl und b0 eine Zahl 0 < b0 < p. Dann existiert eine ein-deutige Folge (b0, b1, . . . , bn, . . .) modulo p mit folgender Eigenschaft: Falls die p-adischeDarstellung einer Zahl x auf bnbn−1 · · · b1b0 endet, dann auch die Darstellung von xp.

Beweis. Gesucht ist also eine Folge b0, b1, . . . , bn, . . . modulo p, sodass für alle n ∈ N gilt:

xn = b0 + b1p+ . . .+ bnpn ≡ xpn mod pn+1

(IA) Bei n = 0 ist uns gerade b0 gegeben. Da b0 < p folgt die Gültigkeit der Aussagex0 = b0 ≡ xp0 mod p nach Fermats2 kleinem Satz.

(IS) Seien nun b1, . . . , bn so gewählt, dass xpn ≡ xn mod pn+1. Wir konstruieren nun eineindeutiges bn+1 sodass

(xn + bn+1pn+1)p ≡ xn + bn+1p

n+1 mod pn+2

Wir betrachten dazu mal die rechte Seite und folgern mit Hilfe des binomischenLehrsatzes

(xn + bn+1pn+1)p = xpn +

(p

1

)xp−1n bn+1p

n+1 + Cpn+2.

Weil(p1

)= p > gilt also

(xn + bn+1pn+1)p ≡ xpn mod pn+2

und wegen der Transitivität der Kongruenz

xn + bn+1pn+1 ≡ xpn mod pn+2 ⇐⇒ xpn − xn − bn+1p

n+1 ≡ 0 mod pn+2.

Nach Induktionsvoraussetzung ist xpn ≡ xn mod pn+1 und somit existiert ein k∗ ∈[k]p = {k + lp|l ∈ Z} mit k∗pn+1 = xpn − xn. Dabei wählen wir k∗ = k denRepräsentanten der Klasse [k]p mit 0 ≤ k < p. Damit ist k eindeutig. Es muss alsofolgende Kongruenz erfüllt sein:

(k − bn+1)pn+1 !≡ 0 mod pn+2 ⇐⇒ k − bn+1 ≡ 0 mod p

woraus man bn+1 = k folgern kann. Damit erfüllt dieses bn+1 die gewünschte Ei-genschaft und der Beweis ist komplett.

2Pierre de Fermat (∗vermutlich Ende 1607 oder Anfang 1608 in Beaumont-de-Lomagne; †12. Januar1665 in Castres) war ein französischer Mathematiker und Jurist. Fermat beschäftigte sich, wie diemeisten Wissenschaftler seiner Zeit, nicht ausschließlich mit der Mathematik. So beschränkte sichsein Einfluss auf die Korrespondenz mit vielen bedeutenden Gelehrten seiner Zeit (wie z. B. Carcavi,Beaugrand, Descartes sowie Mersenne) und auf die von seinem Sohn vorgenommene Ausgabe seinesNachlasses, einschließlich der von ihm kommentierten Arithmetik des Diophant). Er leistete wichtigeBeiträge zur Zahlentheorie, Wahrscheinlichkeitsrechnung, Variations- und Differentialrechnung.

8



3.3 Eine Beispiel aus der Graphentheorie

Satz 7. Jede Landkarte, deren Ländergrenzen durch Geraden gebildet werden, kann durchzwei Farben (schwarz und weiß) so gefärbt werden, dass Länder mit einer gemeinsamenGrenze nicht gleich gefärbt sind.

Man stelle sich dazu also zum Beispiel ein Rechteck (oder eine andere Figur) vor, diekomplett von Geraden durchzogen ist. Diese so entstandenen, von den Geraden begrenz-ten, Flächen sind die Länder.

Beweis. Induktionsvariable ist die Anzahl der Geraden in dieser Karte.

(IA) Wenn wir n = 0 wählen, dann besteht unsere Karte aus genau einem Land und wirkönnen uns aussuchen, wie wir dieses färben möchten. In jedem Fall existiert einezulässige Färbung. Auch bei n = 1 existieren nur zwei Länder auf der Karte, so dasswir eines weiß und das andere schwarz färben, was wiederum zu einer zulässigenFärbung führt.

(IS) Sei nun im folgenden eine Karte mit n Geraden gegeben, welche bereits zulässiggefärbt ist. Wir müssen nun zeigen, dass, wenn wir eine weitere Gerade durch dieseKarte ziehen, jene wieder zulässig gefärbt werden kann. Wir drehen diese Karte so,dass die neue Linie, die wir durchziehen, horizontal verläuft. Dabei kann es nunpassieren, dass diese Gerade einige Länder passiert und andere unberührt lässt.Wir färben nun den Teil oberhalb der neuen Geraden einfach um, also alles wasvorher weiß war färben wir schwarz und umgekehrt. Wir zeigen nun an Fallunter-scheidungen, dass diese Umfärbung eine zulässige Färbung der neuen Karte ergibt.Seien dazu L1 und L2 zwei benachbarte Länder auf der neuen Karte.

1. Fall: Die Länder L1 und L2 liegen beide unterhalb der neuen Geraden. Hier habenwir die Färbung allerdings nicht geändert, also sind sie nach Induktionsvor-aussetzung unterschiedlich gefärbt.

2. Fall: Die Länder L1 und L2 liegen beide oberhalb der neuen Geraden. Hier wurdedie zulässige Färbung nach Induktionsvoraussetzung einfach umgekehrt, alsosind auch diese beiden benachbarten Länder unterschiedlich gefärbt.

3. Fall: Nun nehmen wir ohne Beschränkung der Allgemeinheit an, dass L1 oberhalbund L2 unterhalb der neuen Geraden liegt. Als gemeinsame Grenze habensie nur einen Abschnitt der hinzugenommenen Geraden, sie waren also vorder Umfärbung beide gleich gefärbt. Nun wurde der obere Teil umgefärbt,demnach müssen L1 und L2 nun auch unterschiedlich gefärbt sein.

Damit ist die Behauptung bewiesen.

9



3.4 Ein Beispiel aus der Geometrie

Satz 8. Für jedes n ≥ 4 existiert ein konvexes Polygon mit n Seiten, die nicht allegleich lang sind, so dass die Summe der Abstände eines beliebigen inneren Punktes zuden Seiten eine Konstante ist.

Wir sollen zeigen, dass ein konvexes Polygon mit folgender Eigenschaft existiert: Wennwir von einem beliebigen Punkt P aus dem Inneren dieses n-Gons die Höhen auf die Seitenbilden - diese können im Extremfall ihren Lotfußpunkt auch außerhalb des Polygonshaben - und danach die Beträge ihrer Längen aufsummieren, kommt immer die gleicheKonstante raus. Um den Satz zu beweisen, benötigen wir eine kleine Vorbetrachtung undbeweisen dazu nun als Lemma den Satz von Viviani3.

Lemma 1 (Satz von Viviani). Ist P ein beliebiger Punkt im Inneren eines gleichseitigenDreiecks, so ist die Summe der Abstände dieses Punktes zu den Seiten konstant.

Beweis. Es sei ein gleichseitiges 4ABC mit der Seitenlänge a gegeben. Da das Dreieckgleichseitig ist, sind die Höhen ha alle gleich lang. Der Flächeninhalt des 4ABC lässtsich berechnen über

F =1

2aha.

Sei nun weiter P ein beliebiger Punkt im Inneren dieses Dreiecks, dann betrachten wireine Zerlegung des 4ABC in 4ABP,4BCP und 4APC. Jedes dieser drei Dreieckehat nun a als Grundseite. Die Höhen auf die entsprechenden Seiten bezeichnen wir mitr, p und q. Jede dieser Höhen ist nun der Abstand von P auf eine der Seiten. Wir müssenalso zeigen, dass die Summe r + p + q konstant ist. Aber das ist relativ klar, denn dieFläche des gesamten Dreiecks 4ABC ist gleich der Summe der Flächen der Teildreiecke,lässt sich also berechnen über

F =1

2ar +

1

2ap+

1

2aq.

Es folgt nun weiter:

1

2aha =

1

2a(r + p+ q) =⇒ r + p+ q = ha = const.

Das beweist das Lemma.

Mit Hilfe dieses Lemmas werden wir nun unsere Polygone aus Satz 8 konstruieren. Essei darauf hingewiesen, dass wir in Satz 8 nicht n ≥ 3 fordern, denn im Satz von Vivianihat das Polygon als gleichseitiges Dreieck die Voraussetzung verletzt, dass die Seiten nichtalle gleich lang sind. Wir nutzen Lemma 1 aber zur Konstruktion der Induktionsanfänge.

3Vincenzo Viviani (∗5. April 1622 in Florenz; †22. September 1703 in Florenz) war italienischer Mathe-matiker und Physiker. 1639 wurde er Mitarbeiter von Galileo Galilei. Er verfasste die erste Biografieüber ihn. Des Weiteren rekonstruierte er Schriften von Archimedes und Euklid. 1661 führte er denspäter so bezeichneten Foucaultschen Pendelversuch durch, der fast 200 Jahre später von Foucaultwiederholt und dann nach diesem benannt wurde. 1666 wurde er der Hofmathematiker des Großher-zogs Ferdinand II.

10



Beweis von Satz 8. Wir machen in diesem Beispiel zuerst den Induktionsschritt, da hierdas Konstruktionsverfahren für n-Gone mit solchen Eigenschaften beschrieben werdensoll. Mit Hilfe dieses Verfahrens zeigen wir die Induktionsanfänge.

(IS) Wir machen einen Induktionsschritt der Form n −→ n + 2. Wir betrachten alsoein konvexes Polygon mit n Seiten, die nicht alle gleich lang sind, welches dazudie geforderte Eigenschaft hat. Als nächstes wählen wir uns zwei Parallelen undschneiden damit zwei Ecken des Polygons ab, damit erhalten wir also ein konvexes(n+ 2)-Gon, das, je nach Verschieben der Parallelen, auch nicht alles gleich langeSeiten enthält. Die Summe der Abstände von einem beliebigen Punkt P aus demInneren des neuen Polygons zu den Seiten des ehemaligen n-Gons (auch hier könnendie Lotfußpunkte nun außerhalb des Polygons liegen) ist nach Induktionsvoraus-setzung konstant einer Zahl S1. Was passiert nun mit den Höhen auf die beidenneuen Seiten? Auch diese Summe allein von P aus ist konstant, denn ihre Summeist nichts anderes als der Abstand der beiden Parallelen. Diesen Abstand hattenwir vorher fixiert und die Parallelen gerade so verschoben, dass die zwei Ecken ab-geschnitten werden und so nicht alle Seiten des neuen Polygons gleich lang werden.Dieser Abstand ist nun konstant einer Zahl S2. Die Summe der Abstände zu allenSeiten ist nun S1 + S2 und damit auch wieder konstant.

(IA) Da wir im Induktionsschritt von n nach n + 2 gegangen sind, müssen wir zweiAnfänge bei n = 4 und n = 5machen. Für den Fall n = 4 können wir jedes beliebigeRechteck nehmen, was kein Quadrat ist (Seiten dürfen nicht gleich lang sein!). Dasist ersichtlich mit einer ähnlichen Argumentation wie bei dem Beweis von Lemma1. Das Fünfeck konstruieren wir mit Hilfe des obigen Verfahrens. Dabei starte manmit dem gleichseitigen Dreieck. Dass dabei S1 konstant ist, folgt direkt aus demSatz von Viviani. Der Rest funktioniert wie im Induktionsschritt beschrieben.

4 Induktion bei Internationalen Mathematik-Olympiade

Wir wollen uns nun eine IMO-Aufgabe aus dem Jahre 1988 in Canberra/Australienanschauen. Die Original-Aufgabe lautete wie folgt:

Aufgabe 1. Let a and b be positive integers such that ab+ 1 divides a2 + b2. Show that

a2 + b2

ab+ 1

is the square of an integer.

Offensichtlich ist diese Aussage immer wahr, wenn genau einer der beiden Faktoren0 ist. Aber auch für den Fall, dass a = b = 0 ist, erhalten wir 0 = 02. Wenn man sichdas mal programmiert, dann stellt man fest, dass es unter der Bedingung, dass beideFaktoren kleiner als 100 sein sollen, nur die Tupel (1, 1), (8, 2), (27, 3), (30, 8) und (64, 4)

11



gibt. Wir wollen diese IMO-Aufgabe mit Hilfe des starken Induktionsprinzipes lösen undwerden die Aufgabenstellung ein wenig verschärfen, indem wir genau die Quadratzahlangeben, die für diesen Quotienten herauskommt.

Satz 9. Seien a und b positive natürliche Zahlen für die a2 + b2 durch ab+ 1 teilbar ist.Dann gilt

a2 + b2

ab+ 1= ggT(a, b)2.

Beweis. Wir machen bei der Lösung dieser Aufgabe eine Quasi-Induktion. Die Indukti-onsvariable ist das Produkt ab. Wir machen also eine Induktion über alle Tupel (a, b),die diese Eigenschaft haben.

(IA) Für den Induktionsanfang ab = 1 erhalten wir, dass a = b = 1 sein muss. Damitgilt dann

12 + 12

1 + 1=

2

2= 1 = 12 = ggT(1, 1)2

(IS) Der Induktionsschritt ist nicht allzu einfach. Aber auch das werden wir hinbekom-men. Sei dazu nun ab > 1. Unsere Voraussetzung ist nun, dass wir für alle c, d ∈ Nmit cd+1|c2+d2 und cd < ab bereits wissen, dass c

2+d2

cd+1 = ggT(c, d)2. Wir gehen nunzum nächsten Tupel (a, b) für welches die Zahl ab nicht mehr in die Voraussetzunghineinfällt, aber trotzdem die Eigenschaft ab+1|a2+b2 hat. Unsere Vorgehensweiseist nun wie folgt: Wir zeigen, dass

(i) ∃c ∈ N sodass ac+ 1|a2 + c2

(ii) c < b

(iii) a2+c2

ac+1 = a2+b2

ab+1 und ggT(a, c) = ggT(a, b)

Mit den ersten beiden Punkten gelangen wir zu einem Tupel (a, c) was bereits inder Voraussetzung liegt. Dann können wir über den dritten Punkt zeigen, dass

a2 + b2

ab+ 1=a2 + c2

ac+ 1

IV= ggT(a, c)2 = ggT(a, b)2,

was die Behauptung beweist. Machen wir uns also an die Arbeit, die Punkte (i) bis(iii) zu zeigen.

Ohne Beschränkung der Allgemeinheit sei a ≤ b und wir definieren nun

N 3 q := a2 + b2

ab+ 1> 0.

Wir wollen nun für die Zahl b eine weitere Zahl c so bestimmen, dass der Quotientq derselbe bleibt. Dazu fassen wir b als eine Unbestimmte x auf und erhalten damiteine quadratische Gleichung der Form:

q =a2 + x2

ax+ 1⇐⇒ x2 − qax− q + a2 = 0.

12



Da wir bereits wissen, dass b eine Lösung dieser Gleichung ist, muss die Gleichungalso reduzibel sein, also die Gestalt (x−b)(x−c) haben. Mittels eines Koeffizienten-vergleiches muss nun gelten, dass −(b+c) = −qa, woraus folgt, dass c = qa−b ∈ Zist. Man beachte, dass wir an dieser Stelle wirklich nur sagen können, dass c ∈ Zist. Wir zeigen nun, dass c ∈ N und c < b ist. Es gilt nun

q =a2 + b2

ab+ 1<a2 + b2

ab=a

b+b

a

und weil a ≤ b

aq <a2

b+ b ≤ b2

b+ b = 2b =⇒ c = aq − b < b.

Weil c eine ganze Zahl und q > 0 ist, folgt weiter

q =a2 + c2

ac+ 1=⇒ ac+ 1 > 0 =⇒ c > −1

a

a∈N=⇒ c ≥ 0.

Wir haben nun Punkt (i) und (ii) sowie die Gleichheit der Quotienten in (iii) ge-zeigt. Es fehlt noch zu zeigen, dass ggT(a, c) = ggT(a, b). Wir halten dazu fest, dassdie Beziehung c = qa − b gilt. Da nun ggT(a, b)|a und ggT(a, b)|c folgt, dass auchggT(a, b)|c. Formen wir die Beziehung zu b = qa−c um, dann erhalten wir nach ähn-lichen Überlegungen ggT(a, c)|b. Nach dem Lemma von Bézout4 existieren nun zumeinen x, y ∈ Z mit ggT(a, c) = ax+ by. Da nun gerade ggT(a, b)|a und ggT(a, b)|c,muss also auch ggT(a, b)|ggT(a, c) gelten. Analog gilt ggT(a, c)|ggT(a, b). Damitmuss aber nun folgen, dass ggT(a, b) = ggT(a, b) ist. Damit ist die Aufgabe voll-ständig gelöst.

Bemerkung. Man kann die Aufgabe auch dann lösen, wenn die Quadratzahl nicht be-kannt ist. Ein alternativer Beweis ist in [Sa/An], Seite 166, angegeben.

4Étienne Bézout (∗31. März 1730 in Nemours, Seine-et-Marne; †27. September 1783 in Basses-Loges(nahe Fontainebleau)) war ein französischer Mathematiker.

13



Literatur

[Fo] Otto Forster: Analysis I, Vieweg Verlag, 8.Auflage, 2005

[Sa/An] Svetoslav Savchev und Titu Andreescu: Mathematical Miniatures, The Ma-thematical Association of America, 1. Auflage, 2003

[St] Tobias Strauß: Induktion, Skript eines Vortrages, 2009

14

Documents

Anwendungen der vollständigen Induktion · Matthias Krüger AnwendungendervollständigenInduktion UniversitätRostock InstitutfürMathematik 2 Induktionsprinzipien In diesem Teil