137
2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips Induktion über den rekursiven Aufbau

Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Embed Size (px)

Citation preview

Page 1: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2 Die natürlichen Zahlen und vollständige Induktion

Themen:

◮ Vollständige Induktion

◮ Varianten des Induktionsprinzips

◮ Induktion über den rekursiven Aufbau

Page 2: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.1 Einführung

N = {1, 2, 3, . . .}.sind die natürlichen Zahlen.

Page 3: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.1 Einführung

N = {1, 2, 3, . . .}.sind die natürlichen Zahlen.

Manche Autoren lassen die natürlichen Zahlen auch mit der Nullbeginnen, wir schreiben dafür

N0 = {0, 1, 2, 3, . . .}.

Page 4: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.1 Einführung

N = {1, 2, 3, . . .}.sind die natürlichen Zahlen.

Manche Autoren lassen die natürlichen Zahlen auch mit der Nullbeginnen, wir schreiben dafür

N0 = {0, 1, 2, 3, . . .}.

Die natürlichen Zahlen sind induktiv geordnet: Ausgehend voneinem Anfang, 1 oder 0, erhält man alle natürlichen Zahlen durchden Nachfolger des Anfangs, den Nachfolger des Nachfolgers desAnfangs usw.

Page 5: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Vollständige Induktion – Ein Beispiel

Wir wollen die folgende Formel für die Summe der ersten nungeraden Zahlen beweisen

(An)n∑

k=1

(2k−1) = 1+3+5+. . .+(2n−1) = n2, n = 1, 2, 3, . . . .

Page 6: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Vollständige Induktion – Ein Beispiel

Wir wollen die folgende Formel für die Summe der ersten nungeraden Zahlen beweisen

(An)n∑

k=1

(2k−1) = 1+3+5+. . .+(2n−1) = n2, n = 1, 2, 3, . . . .

n = 1 : 1 = 12

n = 2 : 1 + 3 = 4 = 22

n = 3 : 1 + 3 + 5 = 9 = 32.

Page 7: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Vollständige Induktion – Ein Beispiel

Wir wollen die folgende Formel für die Summe der ersten nungeraden Zahlen beweisen

(An)n∑

k=1

(2k−1) = 1+3+5+. . .+(2n−1) = n2, n = 1, 2, 3, . . . .

n = 1 : 1 = 12

n = 2 : 1 + 3 = 4 = 22

n = 3 : 1 + 3 + 5 = 9 = 32.

Ein Physiker wäre damit schon zufrieden!

Page 8: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Prinzip der vollständigen Induktion

Wir können Aussagen (A1), (A2), . . . mit Hilfe des Prinzips dervollständigen Induktion beweisen. Dazu beweist man zwei Dinge:

(i) (A1) (=Induktionsanfang oder Induktionsverankerung),

(ii) (An) ⇒ (An+1) für alle n ∈ N (=Induktionsschritt).

Page 9: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Prinzip der vollständigen Induktion

Wir können Aussagen (A1), (A2), . . . mit Hilfe des Prinzips dervollständigen Induktion beweisen. Dazu beweist man zwei Dinge:

(i) (A1) (=Induktionsanfang oder Induktionsverankerung),

(ii) (An) ⇒ (An+1) für alle n ∈ N (=Induktionsschritt).

Der zweite Schritt lässt sich so interpretieren: Unter derVoraussetzung, dass wir schon wissen, dass dieInduktionsvoraussetzung (An) richtig ist, können wir auch dieRichtigkeit von (An+1) nachweisen.

Page 10: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Korrektheit der vollständigen Induktion

Wir wenden den modus ponens an:

(A1) = Induktionsanfang

(A1) ⇒ (A2) = Induktionsschritt für n = 1

−−−−−−−−−−−−−−−−−−−−−(A2)

Page 11: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Korrektheit der vollständigen Induktion

Wir wenden den modus ponens an:

(A1) = Induktionsanfang

(A1) ⇒ (A2) = Induktionsschritt für n = 1

−−−−−−−−−−−−−−−−−−−−−(A2)

Durch fortgesetzte Anwendung des modus ponens und unterVerwendung des Induktionsschritts für n = 2, 3, . . . erhält man dieWahrheit von (A3), (A4), . . ..

Page 12: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Der Induktionszug

1 2 3

(An) ⇒ (An+1) bedeutet, dass Waggon n + 1 an Waggon ngekoppelt ist. Fährt nun die Lokomotive los, so rollt der ganze Zug.

Page 13: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Zurück zum Beispiel

(An)n∑

k=1

(2k−1) = 1+3+5+. . .+(2n−1) = n2, n = 1, 2, 3, . . . .

(A1) ist richtig (=Induktionsanfang).

Page 14: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Zurück zum Beispiel

(An)n∑

k=1

(2k−1) = 1+3+5+. . .+(2n−1) = n2, n = 1, 2, 3, . . . .

(A1) ist richtig (=Induktionsanfang).

Induktionsschritt: Sei (An) richtig. Dann

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

=(

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

+ (2(n + 1)− 1)

Page 15: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Zurück zum Beispiel

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

=(

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

+ (2(n + 1)− 1)

Page 16: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Zurück zum Beispiel

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

=(

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

+ (2(n + 1)− 1)

= n2 + (2(n + 1)− 1)

= n2 + 2n + 1 = (n + 1)2.

Damit ist (An) ⇒ (An+1) bewiesen.

Page 17: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Langfassung des Beweises

1 = 12

1 + 3 = 4 = 22

1 + 3 + 5 = (1 + 3) + 5 = 4 + 5 = 9 = 32

1 + 3 + 5 + 7 = (1 + 3 + 5) + 7 = 9 + 7 = 16 = 42

1 + 3 + 5 + 7 + 9 = (1 + 3 + 5 + 7) + 9 = 16 + 9 = 25 = 52

. . .

Im Induktionsschritt führen wir dies in einem Schritt aus.

Page 18: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Aufgabe

Man zeige, dass die vorletzte Ziffer von 3n, n ≥ 1, imDezimalsystem geschrieben geradzahlig ist.

Page 19: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Aufgabe

Man zeige, dass die vorletzte Ziffer von 3n, n ≥ 1, imDezimalsystem geschrieben geradzahlig ist.

Beweis: Für n = 1 ist das der Fall (=Induktionsanfang).

Für den Induktionsschritt ist zu bemerken, dass im Dezimalsystem3n auf 1, 3, 9 oder 7 endet. Mit 3 multipliziert liefern dieseEndziffern den Übertrag 0 oder 2.

Page 20: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Lösung

Ist also die vorletzte Ziffer von 3n geradzahlig, so ist das Dreifacheder vorletzten Ziffer ebenfalls geradzahlig.

Page 21: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Lösung

Ist also die vorletzte Ziffer von 3n geradzahlig, so ist das Dreifacheder vorletzten Ziffer ebenfalls geradzahlig.

Dazu kommt ein geradzahliger Übertrag von der letzten Ziffermultipliziert mit 3. Damit ist auch die vorletzte Ziffer von 3n+1

geradzahlig.

Page 22: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Aufgabe

n Autos stehen auf einer Kreislinie. Die Autos besitzen zusammenso viel Benzin, um damit einmal um den Kreis herumzufahren.Zeigen Sie, dass es ein Auto gibt, das den Kreis einmal umrundenkann, wenn es das Benzin der Autos, bei denen es vorbeikommt,mitnehmen darf.

Page 23: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Aufgabe

n Autos stehen auf einer Kreislinie. Die Autos besitzen zusammenso viel Benzin, um damit einmal um den Kreis herumzufahren.Zeigen Sie, dass es ein Auto gibt, das den Kreis einmal umrundenkann, wenn es das Benzin der Autos, bei denen es vorbeikommt,mitnehmen darf.

Hinweis: Der Einfachheit halber nehme man an, dass das Umrundendes Kreises eine Entfernungseinheit beträgt und dass man dazu eineEinheit Benzin benötigt. Das Auto i erhält ti Benzin mit

∑ti = 1.

Page 24: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Lösung

Beweis durch Induktion über n, die Zahl der Autos.

Page 25: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Lösung

Beweis durch Induktion über n, die Zahl der Autos.

n = 1: geschenkt.

Page 26: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Lösung

Mindestens ein Auto, sagen wir Nummer 1, erreicht mit seinemBenzin das nächste Auto; andernfalls wäre die Summe des Benzinsnicht 1.

Wir entfernen dieses nächste Auto und geben sein Benzin demAuto 1. Nach Induktionsvoraussetzung gibt es nun ein Auto, dasden Kreis umrunden kann. Dieses Auto kann den Kreis auch dannumrunden, wenn man die Ausgangssituation wieder herstellt.

Page 27: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.2 Die Fibonacci-Zahlen

Die Fibonacci-Zahlen Fn sind definiert durch die Anfangsvorgaben

F0 = 0, F1 = 1,

sowie durch die Rekursion

Fn+1 = Fn + Fn−1 für alle n ∈ N.

Page 28: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.2 Die Fibonacci-Zahlen

Die Fibonacci-Zahlen Fn sind definiert durch die Anfangsvorgaben

F0 = 0, F1 = 1,

sowie durch die Rekursion

Fn+1 = Fn + Fn−1 für alle n ∈ N.

Jede Fibonacci-Zahl ist die Summe ihrer beiden Vorgänger:

F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8,

F7 = 13, F8 = 21, F9 = 34, F10 = 55, F11 = 89, F12 = 144.

Page 29: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Modell einer Kaninchenpopulation

Fn sei die Zahl der Paare einer Kaninchenpopulation. JedesWeibchen setzt jeden Monat ein neues Kaninchen in die Welt, dasmit Verzögerung von einem Monat selbst geschlechtsreif wird.

Page 30: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Modell einer Kaninchenpopulation

Fn sei die Zahl der Paare einer Kaninchenpopulation. JedesWeibchen setzt jeden Monat ein neues Kaninchen in die Welt, dasmit Verzögerung von einem Monat selbst geschlechtsreif wird.

Fn+1 = Fn + Fn−1

Paare in n + 1 Paare in n geschlechtsreife Paare in n

Page 31: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum einer Population

Wäre jedes Neugeborene sofort geschlechtsreif, hätten wir dieRekursion Gn+1 = 2Gn, also Gn = 2n.

Page 32: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum einer Population

Wäre jedes Neugeborene sofort geschlechtsreif, hätten wir dieRekursion Gn+1 = 2Gn, also Gn = 2n.

Aufgabe: Bestimme ein möglichst kleines a mit Fn ≤ an.

Page 33: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum einer Population

Wäre jedes Neugeborene sofort geschlechtsreif, hätten wir dieRekursion Gn+1 = 2Gn, also Gn = 2n.

Aufgabe: Bestimme ein möglichst kleines a mit Fn ≤ an.

a ist dann der Wachstumsfaktor der Population.

Page 34: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum der Kaninchen-Population

Idee: Zeige Fn ≤ an durch Induktion über n und benutze dabei(natürlich)

Fn+1 = Fn + Fn−1

und die Induktionsvoraussetzung für Fn und Fn−1.

Page 35: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum der Kaninchen-Population

Idee: Zeige Fn ≤ an durch Induktion über n und benutze dabei(natürlich)

Fn+1 = Fn + Fn−1

und die Induktionsvoraussetzung für Fn und Fn−1.

Der Induktionsanfang muss daher für n = 0 und n = 1nachgewiesen werden.

Page 36: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum der Kaninchen-Population

Induktionsanfang: 0 = F0 ≤ a0 = 1 und 1 = F1 ≤ a1 ist richtig füralle a ≥ 1.

Page 37: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum der Kaninchen-Population

Induktionsanfang: 0 = F0 ≤ a0 = 1 und 1 = F1 ≤ a1 ist richtig füralle a ≥ 1.

Induktionsschritt:

Fn+1 = Fn + Fn−1

IV

≤ an + an−1!

≤ an+1.

Page 38: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum der Kaninchen-Population

Induktionsanfang: 0 = F0 ≤ a0 = 1 und 1 = F1 ≤ a1 ist richtig füralle a ≥ 1.

Induktionsschritt:

Fn+1 = Fn + Fn−1

IV

≤ an + an−1!

≤ an+1.

Wir müssen das minimale a > 0 finden mit

an + an−1 ≤ an+1 ⇔ a + 1 ≤ a2.

Page 39: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum der Kaninchen-Population

an + an−1 ≤ an+1 ⇔ a + 1 ≤ a2.

Page 40: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Wachstum der Kaninchen-Population

an + an−1 ≤ an+1 ⇔ a + 1 ≤ a2.

Das ist die größere der Lösungen der quadratischen Gleichunga2 = a + 1, also

Φ =12+

√5

2= 1.618033 . . . ,

Page 41: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Die Fibonacci-Zahlen in der Natur

34 blau21 rot

Page 42: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.3 Mächtigkeit der Potenzmenge

P(A) = Menge aller Teilmengen von A.

∅,A ∈ P(A).

Page 43: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Hypothese

Bestimme die Anzahl der Teilmengen der MengeAn = {1, 2, . . . , n}!

Page 44: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Hypothese

Bestimme die Anzahl der Teilmengen der MengeAn = {1, 2, . . . , n}!Klar, mit vollständige Induktion über n, aber was sollen wirbeweisen?

Page 45: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Hypothese

Bestimme die Anzahl der Teilmengen der MengeAn = {1, 2, . . . , n}!Klar, mit vollständige Induktion über n, aber was sollen wirbeweisen?

Durch Probieren stellen wir zunächst eine Hypothese auf:

A1 : ∅, {1} 2

A2 : ∅, {1}, {2}, {1, 2} 4

A3 : ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 8

Die Vermutung ist also: An besitzt 2n Teilmengen.

Page 46: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Teile und Herrsche

Für n = 1 ist die Behauptung richtig (=Induktionsanfang).

Page 47: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Teile und Herrsche

Für n = 1 ist die Behauptung richtig (=Induktionsanfang).

Sei 2n die Anzahl der Teilmengen von An

(=Induktionsvoraussetzung).

Strukturiere die zu zählenden Objekte, also die Teilmegen vonAn+1, nach dem Motto „Teile und Herrsche“:

I : Teilmengen, die n + 1 nicht enthalten,

II : Teilmengen, die n + 1 enthalten.

Page 48: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Teile und Herrsche

I : Teilmengen, die n + 1 nicht enthalten,

II : Teilmengen, die n + 1 enthalten.

Gruppe I enthält genau die Teilmengen von An, das sind nachInduktionsvoraussetzung 2n.

Page 49: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Teile und Herrsche

I : Teilmengen, die n + 1 nicht enthalten,

II : Teilmengen, die n + 1 enthalten.

Gruppe I enthält genau die Teilmengen von An, das sind nachInduktionsvoraussetzung 2n.

In den Teilmengen von Gruppe II können wir das Element n + 1weglassen und wir erhalten eine Teilmenge von An.

Page 50: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Teile und Herrsche

I : Teilmengen, die n + 1 nicht enthalten,

II : Teilmengen, die n + 1 enthalten.

Gruppe I enthält genau die Teilmengen von An, das sind nachInduktionsvoraussetzung 2n.

In den Teilmengen von Gruppe II können wir das Element n + 1weglassen und wir erhalten eine Teilmenge von An.

Umgekehrt können wir jede Teilmenge von An durch Anfügen vonn + 1 zu einer Teilmenge von Gruppe II machen.

Page 51: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Teile und Herrsche

I : Teilmengen, die n + 1 nicht enthalten,

II : Teilmengen, die n + 1 enthalten.

Gruppe I enthält genau die Teilmengen von An, das sind nachInduktionsvoraussetzung 2n.

In den Teilmengen von Gruppe II können wir das Element n + 1weglassen und wir erhalten eine Teilmenge von An.

Umgekehrt können wir jede Teilmenge von An durch Anfügen vonn + 1 zu einer Teilmenge von Gruppe II machen.

Damit enthält auch Gruppe II genau 2n Teilmengen, zusammen also2n + 2n = 2n+1.

Page 52: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Mächtigkeit der Potenzmenge

Satz Die Anzahl der Teilmengen einer n-elementigen Menge ist 2n.

Page 53: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.4 Permutationen und Fakultät

Eine Permutation von (1, 2, . . . , n) ist eine Umstellung der Zahlen1, . . . , n.

Page 54: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.4 Permutationen und Fakultät

Eine Permutation von (1, 2, . . . , n) ist eine Umstellung der Zahlen1, . . . , n.

Beispielsweise besitzt (1, 2, 3) die Permutationen

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Page 55: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Alternative Definition

Alternativ kann man die Permutationen als bijektive Abbildungender Menge An = {1, 2, . . . , n} in sich definieren.

Page 56: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Alternative Definition

Alternativ kann man die Permutationen als bijektive Abbildungender Menge An = {1, 2, . . . , n} in sich definieren.

Beispielsweise gehört zur Permutation (2, 3, 1) die Abbildung mit

f (1) = 2, f (2) = 3, f (3) = 1.

Page 57: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Alternative Definition

Alternativ kann man die Permutationen als bijektive Abbildungender Menge An = {1, 2, . . . , n} in sich definieren.

Beispielsweise gehört zur Permutation (2, 3, 1) die Abbildung mit

f (1) = 2, f (2) = 3, f (3) = 1.

Wir stellen uns dabei vor, dass (·, ·, ·) aus nummerierten Kästchenbesteht, in denen wir die Werte von f hineinschreiben.

Page 58: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Fakultät

Für eine Zahl n ∈ N ist n! (gesprochen: n Fakultät) definiert durch

n! = 1 · 2 · · · n.

Page 59: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Fakultät

Für eine Zahl n ∈ N ist n! (gesprochen: n Fakultät) definiert durch

n! = 1 · 2 · · · n.

Die Fakultäten wachsen sehr schnell in n,

3! = 6, 4! = 24, 5! = 120, 6! = 720, 20! = 2.43 . . .× 1018.

Page 60: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Fakultät

Für eine Zahl n ∈ N ist n! (gesprochen: n Fakultät) definiert durch

n! = 1 · 2 · · · n.

Die Fakultäten wachsen sehr schnell in n,

3! = 6, 4! = 24, 5! = 120, 6! = 720, 20! = 2.43 . . .× 1018.

Rein aus praktischen Gründen setzt man 0! = 1.

Page 61: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Anzahl der Permutationen

Satz Die Anzahl der Permutationen von (1, 2, . . . , n) ist n!.

Man kann das durch vollständige Induktion über n beweisen.

Page 62: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Anzahl der Permutationen

Satz Die Anzahl der Permutationen von (1, 2, . . . , n) ist n!.

Man kann das durch vollständige Induktion über n beweisen.

Einfacher ist: Verteile die Zahlen 1, 2, . . . , n auf n nummerierteKästchen.

Page 63: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Anzahl der Permutationen

Satz Die Anzahl der Permutationen von (1, 2, . . . , n) ist n!.

Man kann das durch vollständige Induktion über n beweisen.

Einfacher ist: Verteile die Zahlen 1, 2, . . . , n auf n nummerierteKästchen.

Für die Zahl 1 hat man n Möglichkeiten, für die Zahl 2 sind esn − 1, für die letzte Zahl n verbleibt nur noch eine Möglichkeit.

Page 64: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.5 Binomialkoeffizienten und binomische Formel

Für n ∈ N0 sind die Binomialkoeffizienten folgendermaßen definiert(

n

k

)

=n!

k! (n − k)!für 0 ≤ k ≤ n.

Page 65: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.5 Binomialkoeffizienten und binomische Formel

Für n ∈ N0 sind die Binomialkoeffizienten folgendermaßen definiert(

n

k

)

=n!

k! (n − k)!für 0 ≤ k ≤ n.

Spezialfälle:

( n

0

)

=n!

0! n!= 1,

( n

n

)

=n!

n! 0!= 1.

Page 66: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Die Additionsformel

Lemma (

n

k − 1

)

+

(

n

k

)

=

(

n + 1

k

)

.

Page 67: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir bringen die linke Seite auf den Hauptnenner,(

n

k − 1

)

+

(

n

k

)

=n!

(k − 1)! (n − k + 1)!+

n!

k! (n − k)!

Page 68: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir bringen die linke Seite auf den Hauptnenner,(

n

k − 1

)

+

(

n

k

)

=n!

(k − 1)! (n − k + 1)!+

n!

k! (n − k)!

=n! k

k! (n − k + 1)!+

n!(n − k + 1)k! (n − k + 1)!

=(n + 1)!

k! (n + 1 − k)!=

(

n + 1

k

)

.

Page 69: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Pascalsches Dreieck

n=0 1

n=1 1 1

n=2 1 2 1

n=3 1 3 3 1

n=4 1 4 6 4 1

n=5 1 5 10 10 5 1

Jede neue Zeile wird rechts und links um 1 ergänzt, was den

Werten( n

0

)

und( n

n

)

entspricht, die übrigen Einträge erhält

man aus dem Lemma, jeder Eintrag ist die Summe der links undrechts über ihm stehenden Zahlen.

Page 70: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

k-elementige Teilmengen

Satz Die Zahl der k-elementigen Teilmengen einer n-elementigen

Menge ist( n

k

)

.

Page 71: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir zeigen dies durch vollständige Induktion über n.

Page 72: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir zeigen dies durch vollständige Induktion über n.

Für n = 0 ist die Behauptung richtig, denn die leere Menge enthältnur sich selbst als Teilmenge.

Page 73: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir zeigen dies durch vollständige Induktion über n.

Für n = 0 ist die Behauptung richtig, denn die leere Menge enthältnur sich selbst als Teilmenge.

Die Behauptung ist auch richtig für k = 0 und k = n, in beidenFällen haben wir nur eine Teilmenge, die leere Menge bzw. dieMenge selbst.

Page 74: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir zeigen dies durch vollständige Induktion über n.

Für n = 0 ist die Behauptung richtig, denn die leere Menge enthältnur sich selbst als Teilmenge.

Die Behauptung ist auch richtig für k = 0 und k = n, in beidenFällen haben wir nur eine Teilmenge, die leere Menge bzw. dieMenge selbst.

Nach dem Prinzip „Teile und Herrsche“ strukturieren wir diek-elementigen Teilmengen der Menge An+1 = {1, 2, . . . , n + 1} inzwei Gruppen:

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Page 75: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Page 76: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Gruppe I besteht genau aus den k-elementigen Teilmengen der

Menge An, nach Induktionsvoraussetzung sind das( n

k

)

.

Page 77: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Gruppe I besteht genau aus den k-elementigen Teilmengen der

Menge An, nach Induktionsvoraussetzung sind das( n

k

)

.

In den Teilmengen der Gruppe II können wir das Element n + 1weglassen und erhalten eine k − 1-elementige Teilmenge von An.

Page 78: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Gruppe I besteht genau aus den k-elementigen Teilmengen der

Menge An, nach Induktionsvoraussetzung sind das( n

k

)

.

In den Teilmengen der Gruppe II können wir das Element n + 1weglassen und erhalten eine k − 1-elementige Teilmenge von An.

Umgekehrt können wir jede k − 1-elementige Teilmenge von An umdas Element n + 1 ergänzen und erhalten eine Teilmenge vonGruppe II.

Page 79: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Gruppe I besteht genau aus den k-elementigen Teilmengen der

Menge An, nach Induktionsvoraussetzung sind das( n

k

)

.

In den Teilmengen der Gruppe II können wir das Element n + 1weglassen und erhalten eine k − 1-elementige Teilmenge von An.

Umgekehrt können wir jede k − 1-elementige Teilmenge von An umdas Element n + 1 ergänzen und erhalten eine Teilmenge vonGruppe II.

Nach Induktionsvoraussetzung ist die Zahl der Teilmengen in

Gruppe II gerade( n

k − 1

)

.

Page 80: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Gruppe I:( n

k

)

.

Gruppe II:( n

k − 1

)

.

Page 81: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

I : k-elementige Teilmengen, die n + 1 nicht enthalten,

II : k-elementige Teilmengen, die n + 1 enthalten.

Gruppe I:( n

k

)

.

Gruppe II:( n

k − 1

)

.

Für die Gesamtzahl der Teilmengen gilt daher mit obigem Lemma

Gruppe I + Gruppe II =( n

k

)

+( n

k − 1

)

=( n + 1

k

)

.

Page 82: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel Lotto

Wir bestimmen die Anzahl der 6-elementigen Teilmengen von{1, 2, . . . , 49}:

Page 83: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel Lotto

Wir bestimmen die Anzahl der 6-elementigen Teilmengen von{1, 2, . . . , 49}:

( 496

)

=49!

6! 43!=

49 · (2 · 4 · 6) · 47 · 46 · (3 · 5 · 3) · 441 · 2 · 3 · 4 · 5 · 6

= 49 · 47 · 46 · 3 · 44 = 13 983 816.

Die Wahrscheinlichkeit für sechs Richtige ist daher ungefähr 1 : 14Millionen.

Page 84: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Potenzen im kommutativen Ring

Wir betrachten nun einen kommutativen Ring (R , 0, 1,+, ·).

Page 85: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Potenzen im kommutativen Ring

Wir betrachten nun einen kommutativen Ring (R , 0, 1,+, ·).Wir definieren Potenzen

an = a · a · · . . . · a︸ ︷︷ ︸

n-mal

, a0 = 1.

Page 86: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Potenzen im kommutativen Ring

Wir betrachten nun einen kommutativen Ring (R , 0, 1,+, ·).Wir definieren Potenzen

an = a · a · · . . . · a︸ ︷︷ ︸

n-mal

, a0 = 1.

Für m, n ∈ N0 gelten die Potenzgesetze

am+n = am · an, anbn = (ab)n, (am)n = amn

.

Page 87: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Binomische Formel

Satz Für a, b ∈ R und n ∈ N0 gilt die binomische Formel

(a+b)n =

n∑

i=0

( n

i

)

an−ibi = an+( n

1

)

an−1b+. . .+( n

n − 1

)

abn−1+bn.

Page 88: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Verwenden Induktion über n. Für n = 0 ist die Formel richtig wegena0 = b0 = 1.

Page 89: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Verwenden Induktion über n. Für n = 0 ist die Formel richtig wegena0 = b0 = 1.

Unter der Annahme, dass sie für n richtig ist, folgt

(a+b)n+1 = (a+b)n(a+b) =n∑

i=0

( n

i

)

an−i+1bi+n∑

i=0

( n

i

)

an−ibi+1

Page 90: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

(a+b)n+1 = (a+b)n(a+b) =n∑

i=0

( n

i

)

an−i+1bi+n∑

i=0

( n

i

)

an−ibi+1

Page 91: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Mit Umnummerierung erhalten wir für den ersten Summanden

n∑

i=0

( n

i

)

an−i+1bi = an+1 +

n−1∑

i=0

( n

i + 1

)

an−ibi+1.

Page 92: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Mit Umnummerierung erhalten wir für den ersten Summanden

n∑

i=0

( n

i

)

an−i+1bi = an+1 +

n−1∑

i=0

( n

i + 1

)

an−ibi+1.

(a + b)n+1 = an+1 +n−1∑

i=0

(( n

i + 1

)

+( n

i

))

an−ibi+1 + bn+1.

Page 93: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.6 Modelle

Eine konkrete Menge (mit zugehörigen ausgezeichneten Elementen,Operationen und Relationen), in der die Axiome einermathematischen Struktur gelten, heißt Modell dieser Struktur.

Page 94: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.6 Modelle

Eine konkrete Menge (mit zugehörigen ausgezeichneten Elementen,Operationen und Relationen), in der die Axiome einermathematischen Struktur gelten, heißt Modell dieser Struktur.

Alles, was wir als Beispiele von Gruppen bezeichnet haben, sindModelle der Gruppe. Modelle sind daher konkret. DasAxiomensystem der Gruppe definiert gleichzeitig, was eine Gruppeist.

Page 95: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.6 Modelle

Eine konkrete Menge (mit zugehörigen ausgezeichneten Elementen,Operationen und Relationen), in der die Axiome einermathematischen Struktur gelten, heißt Modell dieser Struktur.

Alles, was wir als Beispiele von Gruppen bezeichnet haben, sindModelle der Gruppe. Modelle sind daher konkret. DasAxiomensystem der Gruppe definiert gleichzeitig, was eine Gruppeist.

In der Mathematik gibt es zwei Arten von Strukturen:

1. Strukturen mit unterschiedlichen Modellen wie Gruppen, Ringe,Körper. Diese werden durch die jeweiligen Axiome definiert, dieman kennen und für die Beweise nutzen muss.

Page 96: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.6 Modelle

2. „Eindeutige“ Strukturen, die im Wesentlichen nur ein Modellbesitzen wie etwa die natürlichen Zahlen. Diese beginnen mit einerWurzel, meist 0 oder 1 genannt, und bestehen aus den Nachfolgernder Wurzel. Abgesehen davon, dass man den Zahlenunterschiedliche Namen geben kann, ist diese Struktur immerdieselbe.

Page 97: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.6 Modelle

2. „Eindeutige“ Strukturen, die im Wesentlichen nur ein Modellbesitzen wie etwa die natürlichen Zahlen. Diese beginnen mit einerWurzel, meist 0 oder 1 genannt, und bestehen aus den Nachfolgernder Wurzel. Abgesehen davon, dass man den Zahlenunterschiedliche Namen geben kann, ist diese Struktur immerdieselbe.

Es gibt keine wirklich verschiedenen Modelle wie etwa bei denGruppen. Weitere Strukturen dieses Typs sind die ganzen, dierationalen und die reellen Zahlen, die später eingeführt werden. Hierbrauchen wir eigentlich keine Axiome, es ist legitim, sich einfach aufden Standpunkt zu stellen, dass man diese Strukturen kennt.

Page 98: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.7 Die Peanoschen Axiome für die natürlichen Zahlen

Die Axiome für die natürlichen Zahlen müssen so formuliert werden,dass es nur ein einziges Modell gibt – eine sportlicheHerausforderung, die der Mathematiker Giuseppe Peano Ende des19. Jahrhunderts erfolgreich angenommen hat.

Page 99: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Die Peanoschen Axiome

In moderner Schreibweise sind die natürlichen Zahlen eine StrukturN = (N, 1, f ) mit dem ausgezeichneten Element 1 und einereinstelligen Abbildung f : N → N, die als Nachfolger interpretiertwird.

Page 100: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Die Peanoschen Axiome

In moderner Schreibweise sind die natürlichen Zahlen eine StrukturN = (N, 1, f ) mit dem ausgezeichneten Element 1 und einereinstelligen Abbildung f : N → N, die als Nachfolger interpretiertwird.

Die Axiome sind dann

(P1) Für alle m, n: Wenn f (m) = f (n), so gilt m = n,

(P2) Es gibt kein n ∈ N mit f (n) = 1,

(P3) Für alle Teilmengen M ⊂ N gilt:

Ist 1 ∈ M und folgt aus n ∈ M, dass auch f (n) ∈ M, so M = N.

Page 101: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

(P1) und (P2)

(P1) Für alle m, n: Wenn f (m) = f (n), so gilt m = n.

Page 102: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

(P1) und (P2)

(P1) Für alle m, n: Wenn f (m) = f (n), so gilt m = n.

f ist injektiv.

Page 103: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

(P1) und (P2)

(P1) Für alle m, n: Wenn f (m) = f (n), so gilt m = n.

f ist injektiv.

(P2) Es gibt kein n ∈ N mit f (n) = 1.

Page 104: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

(P1) und (P2)

(P1) Für alle m, n: Wenn f (m) = f (n), so gilt m = n.

f ist injektiv.

(P2) Es gibt kein n ∈ N mit f (n) = 1.

Insbesondere ist f nicht surjektiv.

Page 105: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

(P1) und (P2)

(P1) Für alle m, n: Wenn f (m) = f (n), so gilt m = n.

f ist injektiv.

(P2) Es gibt kein n ∈ N mit f (n) = 1.

Insbesondere ist f nicht surjektiv.

N kann keine endliche Menge sein, weil f : N → N injektiv undnicht surjektiv sein soll.

Page 106: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Ein Modell von (P1) und (P2)

N = N1 ∪ N2, N1 = {1, 2, 3, . . .}, N2 = {a, b}.

Page 107: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Ein Modell von (P1) und (P2)

N = N1 ∪ N2, N1 = {1, 2, 3, . . .}, N2 = {a, b}.f (n) = n + 1 für n ∈ N1, f (a) = b, f (b) = a.

Page 108: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Ein Modell von (P1) und (P2)

N = N1 ∪ N2, N1 = {1, 2, 3, . . .}, N2 = {a, b}.f (n) = n + 1 für n ∈ N1, f (a) = b, f (b) = a.

f ist injektiv, 1 ist nicht Nachfolger einer Zahl, d.h. (P1) und (P2)sind erfüllt.

Page 109: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Ein Modell von (P1) und (P2)

N = N1 ∪ N2, N1 = {1, 2, 3, . . .}, N2 = {a, b}.f (n) = n + 1 für n ∈ N1, f (a) = b, f (b) = a.

f ist injektiv, 1 ist nicht Nachfolger einer Zahl, d.h. (P1) und (P2)sind erfüllt.

Setze in (P3) M = N1. Dann gilt

1 ∈ M, n ∈ M ⇒ f (n) ∈ M,

aber M 6= N.

Page 110: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Ein Modell von (P1) und (P2)

N = N1 ∪ N2, N1 = {1, 2, 3, . . .}, N2 = {a, b}.f (n) = n + 1 für n ∈ N1, f (a) = b, f (b) = a.

f ist injektiv, 1 ist nicht Nachfolger einer Zahl, d.h. (P1) und (P2)sind erfüllt.

Setze in (P3) M = N1. Dann gilt

1 ∈ M, n ∈ M ⇒ f (n) ∈ M,

aber M 6= N.

(P3) besagt daher, dass N nur aus 1, f (1), f (f (1)), . . . bestehensoll. Unter allen Modellen von (P1),(P2) wird also das minimaleModell ausgewählt.

Page 111: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

2.8 Induktion über den rekursiven Aufbau - Eulersche Polyederformel

Ein (ungerichteter) Graph besteht aus einer Knotenmenge V(engl. vertex) und einer Kantenmenge E (engl. edge). Anschaulichverbindet eine Kante zwei verschiedene Knoten, wobei es auf diegeometrische Form der Kanten meist nicht ankommt.

Page 112: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Eigenschaften von Graphen

◮ Ein Graph heißt zusammenhängend, wenn je zwei Knotendurch einen Kantenzug miteinander verbunden werden können.

◮ Ein Graph heißt planar, wenn er auf der Ebene so gezeichnetwerden kann, dass seine Kanten sich nicht überkreuzen.

◮ Ein Graph heißt nichtleer, wenn er mindestens einen Knotenbesitzt.

Page 113: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiele von Graphen

G G G321 G4

1 2 3

4 5 6

4

1 23

4 5

6G

G2 ist nicht zusammenhängend, die anderen Graphen aber schon.

Page 114: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiele von Graphen

G G G321 G4

1 2 3

4 5 6

4

1 23

4 5

6G

G2 ist nicht zusammenhängend, die anderen Graphen aber schon.

G4 ist planar, weil er kreuzungsfrei gezeichnet werden kann.

Page 115: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiele von Graphen

G G G321 G4

1 2 3

4 5 6

4

1 23

4 5

6G

G2 ist nicht zusammenhängend, die anderen Graphen aber schon.

G4 ist planar, weil er kreuzungsfrei gezeichnet werden kann.

Ein zusammenhängender, planarer Graph unterteilt die Ebene in fFlächen, wobei die Außenfläche mitgezählt wird.

Page 116: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Eulersche Polyederformel

Satz Sei G ein nichtleerer, planarer, zusammenhängender Graphmit f Flächen, e Kanten und v Knoten. Dann gilt

v − e + f = 2.

Page 117: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Der Induktionsanfang ist der Graph, der nur aus einem Knotenbesteht. In diesem Fall ist v = 1, e = 0 und f = 1, alsov − e + f = 2.

Page 118: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Der Induktionsanfang ist der Graph, der nur aus einem Knotenbesteht. In diesem Fall ist v = 1, e = 0 und f = 1, alsov − e + f = 2.

Zum Zeichnen des Graphen benötigen wir die Operationen:

1. Setzen eines neuen Knotens und Verbinden dieses Knotens miteinem alten Knoten. In diesem Fall ändert sich v um +1 und e um+1.

Page 119: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Der Induktionsanfang ist der Graph, der nur aus einem Knotenbesteht. In diesem Fall ist v = 1, e = 0 und f = 1, alsov − e + f = 2.

Zum Zeichnen des Graphen benötigen wir die Operationen:

1. Setzen eines neuen Knotens und Verbinden dieses Knotens miteinem alten Knoten. In diesem Fall ändert sich v um +1 und e um+1.

2. Verbinden zweier Knoten. Hier ändert sich e um +1 und f um+1.

Page 120: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir können jeden nichtleeren, planaren, zusammenhängendenGraphen beginnend mit dem Graphen, der nur aus einem Knotenbesteht, mit den beiden genannten Operationen aufbauen.

Page 121: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beweis

Wir können jeden nichtleeren, planaren, zusammenhängendenGraphen beginnend mit dem Graphen, der nur aus einem Knotenbesteht, mit den beiden genannten Operationen aufbauen.

Die Beziehung v − e + f = 2 ist für den Anfangsgraphen richtigund bleibt nach jedem Schritt bestehen.

Page 122: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Warum Polyederformel?

Für einen Polyeder mit v Knoten, e Kanten und f Seitenflächen istdie Eulersche Polyederformel ebenso richtig.

Page 123: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Folgerungen

Die vollständige Induktion ist ein Beweisprinzip, das für alle rekursivaufgebauten Strukturen geeignet ist:

Page 124: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Folgerungen

Die vollständige Induktion ist ein Beweisprinzip, das für alle rekursivaufgebauten Strukturen geeignet ist:

Natürliche Zahlen, zusammenhängende Graphen, rekursiv definierteFolgen usw.

Page 125: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Folgerungen

Die vollständige Induktion ist ein Beweisprinzip, das für alle rekursivaufgebauten Strukturen geeignet ist:

Natürliche Zahlen, zusammenhängende Graphen, rekursiv definierteFolgen usw.

Beim Induktionsanfang müssen alle „Wurzeln“ der rekursivenStruktur berücksichtigt werden. Beispiel: Bei den Fibonacci-Zahlensind das F0 und F1.

Page 126: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Invariante

Man nennt v − e + f = 2 eine Invariante, weil sie sich nicht ändert,wenn man einen Graphen verändert, so lange er nichtleer,zusammenhängend und planar bleibt.

Page 127: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Es gibt 11 rote, 4 blaue und und 6 gelbe Chamäleons.

Page 128: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Es gibt 11 rote, 4 blaue und und 6 gelbe Chamäleons.

Treffen zwei Chamäleons verschiedener Farbe aufeinander, sonehmen sie die dritte Farbe an. Z.B. entstehen aus einem roten undeinem blauen Chamäleon zwei gelbe.

Page 129: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Es gibt 11 rote, 4 blaue und und 6 gelbe Chamäleons.

Treffen zwei Chamäleons verschiedener Farbe aufeinander, sonehmen sie die dritte Farbe an. Z.B. entstehen aus einem roten undeinem blauen Chamäleon zwei gelbe.

Ist es möglich, dass am Ende alle Chamäleons die gleiche Farbebesitzen?

Page 130: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Wir schreiben rote, blaue und gelbe Chamäleons als 3-tupel(r , b, g). Den beschriebenen Farbwechseln entsprechen dann diedrei Operationen

(r , b, g) → (r − 1, b − 1, g + 2), (r , b, g) → (r − 1, b + 2, g − 1),

(r , b, g) → (r + 2, b − 1, g − 1).

Page 131: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Wir suchen eine Invariante, die nur 2 Farben betrifft:

(r , b) → (r−1, b−1), (r , b) → (r−1, b+2), (r , b) → (r+2, b−1).

Page 132: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Wir suchen eine Invariante, die nur 2 Farben betrifft:

(r , b) → (r−1, b−1), (r , b) → (r−1, b+2), (r , b) → (r+2, b−1).

Die Differenz r − b bleibt gleich oder verändert sich um ±3.

Page 133: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Wir suchen eine Invariante, die nur 2 Farben betrifft:

(r , b) → (r−1, b−1), (r , b) → (r−1, b+2), (r , b) → (r+2, b−1).

Die Differenz r − b bleibt gleich oder verändert sich um ±3.

Bei r = 11, b = 4 erhalten wir 11 − 4 = 7.

Page 134: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Wir suchen eine Invariante, die nur 2 Farben betrifft:

(r , b) → (r−1, b−1), (r , b) → (r−1, b+2), (r , b) → (r+2, b−1).

Die Differenz r − b bleibt gleich oder verändert sich um ±3.

Bei r = 11, b = 4 erhalten wir 11 − 4 = 7.

Ist die geforderte Endposition r = 21, so ist 21 − 0 = 21.

Page 135: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips

Beispiel

Wir suchen eine Invariante, die nur 2 Farben betrifft:

(r , b) → (r−1, b−1), (r , b) → (r−1, b+2), (r , b) → (r+2, b−1).

Die Differenz r − b bleibt gleich oder verändert sich um ±3.

Bei r = 11, b = 4 erhalten wir 11 − 4 = 7.

Ist die geforderte Endposition r = 21, so ist 21 − 0 = 21.

Ist sie g = 21, so 0 − 0 = 0. Man kann also die Endposition mit 21gleichfarbigen Chamäleons nicht erreichen.

Page 136: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips
Page 137: Themen: Vollständige Induktion Varianten des ...dobro/inf2/f2.pdf · 2 Die natürlichen Zahlen und vollständige Induktion Themen: Vollständige Induktion Varianten des Induktionsprinzips