Analysis 1 WS1516 Übungsblätter PDF

Preview

Summary

WS15/16...

Description

Zentrum Mathematik Prof. Dr. Daniel Matthes Dr. Carl-Friedrich Kreiner

Technische Universit¨ at M¨ unchen WS 2015/16 Blatt 1

Analysis 1 — L¨ osungsvorschl¨ age zu den Diskussionsaufgaben —

D 1. Vollst¨ andige Induktion Zeigen Sie: (a) F¨ ur jedes n ∈ N gilt

n P

k=0

k 2 = 16 n(n + 1)(2n + 1).

(b) F¨ ur alle n ∈ N und f¨ur alle x 6= 1 gilt

n   1 − x2n+1 Y k 1 + x2 = . 1−x k=0

Zur L¨ osung. (a) F¨ ur n = 0 ist gezeigt.

0 P

k 2 = 02 = 0 und

k=0

1 6

· 0 · (0 + 1)(0 + 1) = 0; damit ist der Induktionsanfang

n P Nun zum Induktionsschritt von n auf n+1. Unter der Annahme, dass k 2 = 16 n(n + 1)(2n + 1) n+1 k=0 P 2 1 wahr ist (Induktionsannahme), muss k = 6 (n + 1)(n + 2)(2n + 3) gezeigt werden. k=0 Dazu rechnen wir n+1 X

k2 =

k=0

= =

n X

k 2 + (n + 1)2

Ind.Ann. 1 = 6

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

k=1   1 (n + 1) n(2n + 1) + 6(n + 1) = 16 (n + 1)(2n2 + n + 6n + 6) 6 1 (n + 1)(2n2 + 4n + 3n + 6) = 16 (n + 1)(n + 2)(2n + 3). 6

(b) Induktionsverankerung n = 0: Es gilt 0   Y 1 − x2 k , 1 + x2 = 1 + x1 = 1−x k=0

also ist die Behauptung wahr f¨ur n = 0. Induktionsschritt von n − 1 auf n: F¨ur jedes n ≥ 1 gilt  n 2 n+1 n      2n Y Y  n−1  1 − x2 1 − x2 2k 2n 2k 2n 1 − x 1+x = 1+x = , 1+x = 1+x = 1−x 1−x 1−x k=0

k=0

wobei beim zweiten Gleichheitszeichen die Induktionsannahme verwendet wurde. D 2. Vokabeltraining (a) Seien A und B Aussagen, f¨ur die die Implikation A ⇒ B gilt. Welche der folgenden Aussagen sind dann sicher wahr? (i) A ⇔ B (ii) A (iii) B (iv) A ist hinreichend f¨ur B (v) A ist notwendig f¨ur B (vi) B ⇒ A 1

(vii) A ∧ B (viii) (¬A) ∨ B (mit Wahrheitstafeln arbeiten!) (ix) ¬B ⇒ ¬A (wird in H1 fortgesetzt) (b) Schreiben Sie die folgenden Aussagen mit Quantoren. • F¨ ur jede nat¨ urliche Zahl n ist auch n + 1 eine nat¨urliche Zahl. • 111 hat noch andere Teiler außer 1 und 111. ur geeignete ganzzahlige x liegt 2x zwischen 100 und 1000. • F¨ • Einige nat¨ urliche Zahlen haben mehr als zwei verschiedene Teiler. asst sich mit zwei ganzen Zahlen z1 und z2 in der Form x = zz12 • Jede rationale Zahl x l¨ darstellen. ¨ bersetzen Sie die folgenden Aussagen in Umgangssprache und entscheiden Sie (mit Schulwis(c) U sen), welche davon wahr sind. • ∀ z ∈ Z : z3 ∈ N • ∀ n ∈ N : n1 ∈ Q • ∃q ∈Q: 0·q =1 (d) Negieren Sie die Aussagen in (c). Zur L¨ osung. (a) Alle Gegenbeispiele werden illustriert durch die Aussagen “n durch 6 teilbar” (A) und “n durch 3 teilbar” (B), indem f¨ur n verschiedene Zahlen eingesetzt werden. F¨ur jedes n gilt A ⇒ B. (i) I.a. falsch, denn ⇔ folgt nicht aus ⇒. Gegenbeispiel: Setze n = 9. (ii) I.a. falsch, setze n = 9: A ist falsch, B ist wahr (und A ⇒ B ist ohnehin wahr). (iii) I.a. falsch, setze n = 7: B ist falsch, A ebenfalls (aber A ⇒ B gilt, da aus einer falschen Aussage alles gefolgert werden kann, s. Vorl.). (iv) Wahr, denn so kann man A ⇒ B mit Worten ausdr¨ucken (s. Vorl.). (v) I.a. falsch, denn das ist dieselbe Aussage wie B ⇒ A, also siehe (i) und (vi). (vi) I.a. falsch, setze wieder n = 9. (vii) I.a. falsch, da weder A noch B wahr sein m¨ussen, siehe (ii) und (iii). (viii) Wahr, denn die beiden Wahrheitstafeln A B ¬A (¬A) ∨ B W W F W W F F F F W W W F F W W

und (siehe Vorl.)

A W W F F

B W F W F

A⇒B W F W W

haben dieselbe letzte Spalte. (ix) Wahr. Das wurde in der Vorlesung erw¨ahnt und ist durch Vergleich der Wahrheitstafeln in H 1 zu beweisen. (b) • ∀ n ∈ N : (n + 1) ∈ N. • ∃ n ∈ N : 1 < n < 111 ∧ n | 111. • ∃ x ∈ Z : 100 < 2x < 1000. • ∃ n ∈ N ∃ p ∈ N : p | n ∧ p 6∈ {1, n}. • ∀ x ∈ Q ∃ z1 , z2 ∈ Z : x = zz21 . (c) • “Die dritte Potenz einer ganzen Zahl ist stets eine nat¨urliche Zahl.” Diese Aussage ist falsch, weil beispielsweise −1 ∈ Z, aber (−1)3 = −1 6∈ N. • “Der Kehrwert jeder nat¨ urlichen Zahl ist eine rationale Zahl.” Diese Aussage ist aufgrund der in der Vorlesung festgelegten Konvention 0 ∈ N falsch, weil (nach Schulwissen) 10 6∈ Q. • “Es gibt eine rationale Zahl q, f¨ur die 0 · q = 1 gilt. Diese Aussage ist falsch (siehe vorige Aussage). (d) Durch Negation werden aus den falschen Aussagen in (c) nat¨urlich jetzt wahre Aussagen und umgekehrt. Wie in der Vorlesung ausgef¨uhrt, erh¨ alt man die Negation der ganzen Aussage durch Umkehrung aller Quantoren und Negation der Gleichungen/Ungleichungen/. . . 2

• ∃z ∈ Z : z 3 6∈ N oder in Worten: “Es gibt eine ganze Zahl, deren dritte Potenz keine nat¨ urliche Zahl ist.” • ∃n ∈ N : n1 6∈ Q • ∀q ∈ Q : 0 · q 6= 1 oder z.B. in Worten: “Es gibt keine rationale Zahl, deren Produkt mit 0 das Ergebnis 1 liefert.”

3

Zentrum Mathematik Prof. Dr. Daniel Matthes Dr. Carl-Friedrich Kreiner

Technische Universit¨ at M¨ unchen WS 2015/16 Blatt 1

Analysis 1 ¨ — — L¨ osungsvorschl¨ age zu den abgegebenen Ubungsaufgaben

H 1. Leichte Schreibarbeit (a) Schreiben Sie ohne Summenzeichen und berechnen Sie: (b) Schreiben Sie mit Summenzeichen: (c) Schreiben Sie mit Summenzeichen:

3

 52

7 P

k=3

2k . k!

6 + 74 + 59 + 11 .     6 6   8 8  20 2 4 4 · · · · · + 1 3 3 5 + 5 7 + 7 9 + · · · + 19

20 21



.

(d) Seien A und B Aussagen. Zeigen Sie durch Vergleich von Wahrheitstafeln, dass die Aussagen A ⇒ B und ¬B ⇒ ¬A ¨aquivalent sind. L¨ osungsvorschlag. 7 P 2k 32 64 128 (a) . = 86 + 16 + 120 + 720 + 5040 = 50 21 k! 24 k=3 6 P k 6 (b) 35 + 47 + 59 + 11 . = 2k−1 k=3 2 2  4 4  6 6  8 8   (c) 1 · 3 + 3 · 5 + 5 · 7 + 7 · 9 + · · · + 20 · 19

20 21



=

10 P

k=1

(2k)2 . (2k−1)(2k+1)

(d) Aus der in der Vorlesung eingef¨uhrten Wahrheitstafel f¨ur ⇒” ” A B W W W F F W F F

A⇒B W F W W

A W W F F

ergibt sich

B W F W F

¬B ¬A F F W F F W W W

(¬B) ⇒ (¬A) W F W W

und die ersten beiden und die letzten Spalten der beiden Tafeln stimmen ¨uberein. H 2. Vollst¨ andige Induktion I Zeigen Sie durch Induktion nach n: (a) F¨ur alle n ∈ N und f¨ur alle x 6= 1 gilt n X

xk =

k=0

(b) F¨ur alle n ∈ N gilt

1 − xn+1 1−x

2n X (−1)k+1 k=1

k

=

(geometrische Summenformel). n X k=1

1 . n+k

L¨ osungsvorschlag. (a) Induktionsanfang n = 0: Es gilt 0 X

xk = x0 = 1 =

k=0

1 − x1 , 1−x

also ist die Behauptung wahr f¨ur n = 0. Das gilt insbesondere auch im Fall x = 0, da man n Q x). 00 = 1 setzt (wg. Konvention ¨uber leere Produkte: Potenzen sind definiert durch xn = k=1

1

Induktionsschritt von n − 1 auf n: F¨ur jedes n ≥ 1 gilt n X

xk =

n−1 X

xk + xn =

k=0

k=0

1 − xn 1 − xn+1 1 − xn + xn − xn+1 , + xn = = 1−x 1−x 1−x

n−1 P k wobei beim zweiten Gleichheitszeichen die Induktionsvoraussetzung x = k=0 det wurde. (b) Induktionsanfang: F¨ ur n = 0 steht auf beiden Seiten die leere Summe. Induktionsschritt n → n + 1: Zu zeigen ist, dass aus der Gleichung 2n X (−1)k+1 k=1

=

k

n X k=1

folgt. Einerseits gilt

1 n+k

2(nP +1) k=1

n+1 X k=1

2(X n+1) k=1

(−1)k+1 k

=

2n P

k=1

(−1)k+1 k

verwen-

n+1

X 1 (−1)k+1 = k n+1+k k=1

+1 −1 + 2n+1 + 2n+2 , andererseits ist mit j = k + 1

  n n+2 X X 1 1 1 1 1 1 1 1 + + − − . + = = 2n + 1 2n + 2 n + 1 n + 1 j=1 n + j n + 1 + k j=2 n + j n + 1

Wegen 2(n +1) P k=1

die Gleichung

1−xn 1−x

−1 2n+2

(−1)k+1 k

=

1 2n+2

=

2n P

k=1

−

1 n+1

(−1)k+1 k

folgt mit der Induktionsvoraussetzung  P  n 1 +1 − 2n+2 = + 2n+1

j=1



1 1 + 2n+1 n+j

+

1 2n+2

−

1 n+1



=

n+1 P k=1

1 n+1+k

also die Behauptung. H 3. Vollst¨ andige Induktion II Zeigen Sie durch Induktion: (a) F¨ur jedes n ∈ N ist 5n + 7 durch 4 teilbar. (b) Die Summe der dritten Potenzen dreier aufeinanderfolgender nat¨urlicher Zahlen ist stets durch 9 teilbar. L¨ osungsvorschlag. (a) Induktionsanfang n = 0: Die Zahl 50 + 7 = 1 + 7 = 8 ist durch 4 teilbar, da 8 = 2 · 4. Induktionsschritt von n auf n + 1: Es gilt 5n+1 + 7 = 5 · 5n + 35 − 35 + 7 = 5 · (5n + 7) − 28. Nach Induktionsvoraussetzung ist der Ausdruck in der Klammer und damit der ganze erste Summand durch 4 teilbar; der zweite Summand 28 ist ebenfalls durch 4 teilbar. Somit ist auch die ganze Summe 5n+1 + 7 durch 4 teilbar. (b) Die Behauptung ist, dass n3 + (n + 1)3 + (n + 2)3 f¨ur jedes n ∈ N durch 9 teilbar ist. Induktionsanfang n = 0: Die Zahl 03 + 13 + 23 = 1 + 8 = 9 ist durch 9 teilbar. Induktionsschritt von n − 1 auf n: Die Induktionsannahme ist, dass an−1 := (n − 1) 3 + n3 + (n + 1)3 durch 9 teilbar ist, und zu zeigen ist, dass dasselbe f¨ur n3 + (n + 1)3 + (n + 2)3 gilt. Sei also n ≥ 1 beliebig und die Induktionsannahme erf¨ullt. Wegen (a + b)3 = a3 + 3a2 b + 3ab2 + b3 gilt nun aber n3 + (n + 1)3 + (n + 2)3 = an−1 − (n − 1)3 + (n + 2)3 = an−1 − (n3 − 3n2 + 3n − 1) + (n3 + 6n2 + 12n + 8) = an−1 + 9n2 + 9n + 9. Jeder der vier Summanden ist durch 9 teilbar (der erste davon nach Induktionsannahme) und somit auch n3 + (n + 1)3 + (n + 2)3 . 2

,

H 4. Kalussen auf Salabinga Im Rahmen einer biologischen Studie ¨uber Eigenschaften der Kalussenvorkommen auf der S¨udseeinsel Salabinga kamen Wissenschaftler zu folgendem Ergebnis: Es gibt dorige Kalussen. Jede ” fabulente Kalusse ist dorig. Auch jede nichtbruchselnde Kalusse ist dorig, aber es gibt auch undorige Kalussen.“ Aus fr¨ uheren Studien war bereits bekannt, dass sich f¨ur jede Kalusse v¨ollig zweifelsfrei feststellen l¨asst, ob sie dorig, fabulent und/oder bruchselnd ist. Es bezeichne K die Menge aller Kalussen. F¨ur eine Kalusse k ∈ K bezeichne D(k) die Aussage ur k ist fabulent“ und B(k) f¨ ur k ist bruchselnd“ . Die ersten k ist dorig“ ; analog stehe F (k) f¨ ” ” ” beiden aus der Studie zitierten S¨atze k¨ onnen dann in folgender Weise formalisiert werden: ∃ k ∈ K : D(k)

(1. Satz)

bzw.

∀ k ∈ K : F (k) ⇒ D(k)

(2. Satz).

(a) Formulieren Sie die ¨ubrigen Aussagen aus der Studie mithilfe von ¬, ∃, ∀, ⇒ usw. (b) Formulieren Sie auch die nachfolgenden Aussagen mithilfe von Quantoren und Implikationen und entscheiden Sie, welche dieser Aussagen aus der Studie gefolgert werden k¨onnen: (i) Es gibt sowohl bruchselnde als auch nichtbruchselnde Kalussen. (ii) Alle undorigen Kalussen sind bruchselnd. (iii) Es gibt bruchselnde Kalussen, die unfabulent sind. L¨ osungsvorschlag. Wir k¨ urzen die Aussage ∃ k ∈ K : D(k) mit [1] und die Aussage ∀ k ∈ K : F (k) ⇒ D(k) mit [2] ab. (a) Der Halbsatz jede nichtbruchselnde Kalusse ist dorig“ besagt ∀ k ∈ K : ¬B(k) ⇒ D(k) [3]. ” Der Halbsatz es gibt undorige Kalussen“ besagt ∃ k ∈ K : ¬D(k) [4]. ” (b) (i) Aussage (i) besagt (∃ k ∈ K : B(k) ) ∧ (∃ k ∈ K : ¬B (k) ). Das kann nicht aus den zur Verf¨ugung stehenden Aussagen [1]–[4] gefolgert werden. Zur Begr¨undung geben wir ein Beispiel f¨ur eine Menge K an, die alle Aussagen aus der Studie erf¨ullt, in der aber keine nichtbruchselnden Kalussen vorkommen: K = {k1 , k2 }, worin k1 bruchselnd, fabulent und dorig ist und k2 bruchselnd, unfabulent und undorig ist. (ii) Aussage (ii) besagt ∀ k ∈ K : ¬D(k) ⇒ B(k). Diese Aussage kann aus der Studie gefolgert werden. Denn angenommen, Aussage (ii) sei falsch. Dann g¨abe es undorige Kalussen, die nichtbruchselnd sind, im Widerspruch zu [3]. (iii) Aussage (iii) besagt ∃ k ∈ K : B(k) ∧ ¬F (k). Diese Aussage kann aus der Studie gefolgert werden, denn: Wegen [4] gibt es undorige Kalussen. Diese sind wegen [2] unfabulent und wegen (ii) bruchselnd.

3

Zentrum Mathematik Prof. Dr. Daniel Matthes Dr. Carl-Friedrich Kreiner

Technische Universit¨ at M¨ unchen WS 2015/16 Blatt 2

Analysis 1 — L¨ osungsvorschl¨ age zu den Diskussionsaufgaben —

D 3. Quantorenketten ¨ Sie die folgenden Aussagen in Umgangssprache und entscheiden Sie, welche davon (a) Ubersetzen wahr sind. (i) ∀ z ∈ Z ∃ n ∈ N : z 2 = n2 (ii) ∃ z ∈ Z ∃ n ∈ N : z 2 = n2 (iii) ∀ z ∈ Z ∃ n ∈ N : z + n = 0 (iv) ∃ z ∈ Z ∀ n ∈ N : z < n (v) ∀ z ∈ Z ∀ n ∈ N : z < n (vi) ∀ z ∈ Z ∀ n ∈ N : z · n ∈ Z (b) Negieren Sie die Aussagen in (a). Zur L¨ osung. (a) (i) “Zu jeder ganzen Zahl z gibt es eine nat¨urliche Zahl n mit der Eigenschaft, dass z 2 und n2 ¨ubereinstimmen.” Diese Aussage ist wahr; setze n = |z|. (ii) “Es gibt eine ganze Zahl z und eine nat¨urliche Zahl n, deren Quadrate ¨ubereinstimmen.” Diese Aussage ist wahr; man kann zum Beispiel z = n = 1 nehmen (oder sich irgendeine andere nat¨urliche Zahl k aussuchen und z = n = k setzen). Letztlich folgt die Aussage aus der Kombination von N ⊂ Z und N 6= ∅. (iii) “Zu jeder ganzen Zahl kann man eine nat¨urliche Zahl mit der Eigenschaft finden, dass die Summe der beiden Zahlen Null ergibt.” Diese Aussage ist falsch, wie man am Beispiel z = 1 sieht. Um z + n = 0 zu l¨osen, m¨ usste man n = −1 setzen, aber (−1) 6∈ N. (iv) “Es gibt eine ganze Zahl, die kleiner als jede nat¨urliche Zahl ist.” Diese Aussage ist wahr; man kann zum Beispiel z = −123 nehmen. (v) “Jede ganze Zahl ist kleiner als jede nat¨urliche Zahl.” Diese Aussage ist falsch, beispielsweise f¨ ur die Kombination z = 2 und n = 1. (vi) “Das Produkt einer ganzen Zahl und einer nat¨urlichen Zahl ist stets eine ganze Zahl.” Diese Aussage ist nach den bekannten Eigenschaften der Multiplikation wahr. (b) Durch Negation werden aus den wahren Aussagen in (c) nat¨urlich jetzt falsche Aussagen und umgekehrt. Wie in der Vorlesung ausgef¨uhrt, erh¨ alt man die Negation der ganzen Aussage durch Umkehrung aller Quantoren und Negation der Gleichungen/Ungleichungen/. . . (i) ∃ z ∈ Z ∀ n ∈ N : z 2 6= n2 oder in Worten: “Es gibt eine ganze Zahl z, deren Quadrat niemals das Quadrat einer nat¨urlichen Zahl ist.” (ii) ∀ z ∈ Z ∀ n ∈ N : z 2 6= n2 oder in Worten: “Das Quadrat einer ganzen Zahl ist niemals gleich dem Quadrat einer nat¨urlichen Zahl.” (iii) ∃ z ∈ Z ∀ n ∈ N : z + n 6= 0 oder in Worten: “Es gibt eine ganze Zahl, die man zu jeder nat¨ urlichen Zahl addieren kann, ohne als Ergebnis Null zu erhalten.” Das erf¨ullt jede positive Zahl z . (iv) ∀ z ∈ Z ∃ n ∈ N : z ≥ n oder in Worten: “Zu jeder ganze Zahl kann man eine nat¨urliche Zahl finden, die kleiner ist.” (v) ∃ z ∈ Z ∃ n ∈ N : z ≥ n oder in Worten: “Es gibt eine ganze Zahl z und eine nat¨urliche Zahl n, die z > n erf¨ ullen.” Ein Beispiel f¨ur solche Zahlen wurde schon in (c) genannt, n¨ amlich z = 2, n = 1. (vi) ∃ z ∈ Z ∃ n ∈ N : z · n 6∈ Z oder in Worten: “Es gibt eine ganze Zahl und eine nat¨urliche Zahl, deren Produkt keine ganze Zahl ist.” 1

D 4. Logik Seien A, B und C Aussagen. Zeigen Sie: (a) A ∨ (B ∧ C) ist a¨quivalent zu (A ∨ B) ∧ (A ∨ C). (b) A ∧ (B ∨ C) ist aquivalent zu (A ∧ B) ∨ (A ∧ C). ¨ (c) ¬(A ∨ B) ist ¨aquivalent zu ¬A ∧ ¬B . Zur L¨ osung. (a) Die entsprechenden Wahrheitstafeln stimmen ¨uberein: A W W W W F F F F

B W W F F W W F F

C W F W F W F W F

B ∧ C A ∨ (B ∧ C) W W F W F W F W W W F F F F F F

und

A W W W W F F F F

B W W F F W W F F

C W F W F W F W F

A ∨ B A ∨ C (A ∨ B) ∧ (A ∨ C) W W W W W W W W W W W W W W W W F F F W F F F F

C W F W F W F W F

A ∧ B A ∧ C (A ∧ B) ∨ (A ∧ C) W W W W F W F W W F F F F F F F F F F F F F F F

(b) Die entsprechenden Wahrheitstafeln stimmen ¨uberein: A W W W W F F F F

B W W F F W W F F

C W F W F W F W F

B ∨ C A ∧ (B ∨ C) W W W W W W F F W F W F W F F F

und

A W W W W F F F F

B W W F F W W F F

(c) Die entsprechenden Wahrheitstafeln stimmen ¨uberein: A W W F F

B W F W F

A ∨ B ¬(A ∨ B) W F W F W F F W

A W W F F

und

B W F W F

¬A ¬B ¬A ∧ ¬B F F F F W F W F F W W W

D 5. Potenzmenge (a) Sei A = {1, 2}. Geben Sie P(A) und P(P(A)) an. (b) Sei n eine nat¨urliche Zahl und n ≥ 1. Zeigen Sie durch vollst¨andige Induktion, dass die Menge {1, 2, . . . , n} genau 2n Teilmengen hat. Zur L¨ osung.   (a) Nach Definition der Potenzmenge ist P(A) = ∅, {1}, {2}, {1, 2} . Diese vierelementige Menge hat sechzehn Teilmengen (das sind jeweils Mengen, deren Elemente wiederum Mengen sind), n¨ amlich • eine mit null Elementen: ∅, • vier mit einem Element: {∅}, {{1}}, {{2}}, {A} • sechs mit zwei Elementen: {∅, {1}}, {∅, {2}}, {∅, A}, {{1}, {2}}, {{1}, A}, {{2}, A}, • vier mit drei Elementen: {∅, {1}, {2}}, {∅, {1}, A}, {∅, {2}, A}, {{1}, {2}, A} • eine mit vier Elementen: P(A). Diese sechzehn Mengen bilden P(P(A)), also die Potenzmenge von P(A). 2

(b) Induktionsanfang n = 1: Eine einelementige Menge besitzt 21 = 2 Teilmengen, n¨amlich die leere Menge ∅ und sich selbst. Induktionsschritt n → n + 1: Nach Induktionsannahme hat die Menge {1, 2, . . . , n} genau 2n Teilmengen, sagen wir M1 , . . . , M2n , und das sind zugleich genau diejenigen Teilmengen von M , die n + 1 nicht als Element enthalten. Die Mengen M2n +1 = M1 ∪ {n + 1}, M2n +2 = M2 ∪ {n + 1}, . . . , M2n +2n = M2n ∪ {n + 1} sind Teilmengen von M . Außerdem sind das genau diejenigen Teilmengen von M , die n + 1 als Element enthalten – denn aus jeder solchen Teilmenge kann man n + 1 entfernen und dadurch eine Teilmenge von {1, 2, . . . , n} bekommen. Also stellen die (paarweise verschiedenen) 2n+1 Mengen M1 , . . . , M2n+1 alle Teilmengen von M dar. D 6. Fehlersuche im Induktionsbeweis In dieser Aufgabe wird vereinfachend angenommen, dass sich f¨ur jedes Auto eindeutig entscheiden l¨ asst, ob es rot ist oder nicht. Finden Sie den Fehler in der folgenden Argumentation: Satz: Auf jedem Parkplatz stehen entweder nur rote Autos oder nur nichtrote Autos. Beweis: Sei P ein beliebiger Parkplatz und n ∈ N die Anzahl der auf P geparkten Autos. Der Beweis erfolgt mittels vollst¨andiger Induktion nach n. Der Fall n = 0 ist trivial. (Wenn wir den Satz nur f¨ ur nicht leere Parkpl¨atze beweisen m¨ochten, beginnen wir mit n = 1. Ein einzelnes Auto ist entweder rot oder nicht, also ist die Behauptung f¨ur n = 1 wahr.) F¨ur den Induktionsschritt (n − 1) → n mit n ≥ 1 d¨urfen wir annehmen, dass die Aussage f¨ur alle Parkpl¨atze mit n − 1 Autos wahr ist, und m¨ussen die Aussage f¨ur einen Parkplatz mit n Autos beweisen. Sei also P ein Parkplatz, auf dem n Autos geparkt sind. Davon lassen wir eines (sagen wir: Auto a) abschleppen; dann sind auf P nur noch n − 1 Autos geparkt, und wir k¨onnen die Induktionsvoraussetzung anwenden. Die n − 1 verbliebenen Autos sind also entweder alle rot oder alle nichtrot. Wir betrachten eines der verbliebenen Autos (sagen wir: Auto b) und stellen fest, ob es rot ist oder nicht. Dieselbe Eigenschaft haben dann alle ¨ubrigen Autos c1 , c2 , . . . . Jetzt rufen wir wieder den Abschleppdienst, lassen b abschleppen und a zur¨uckstellen. Damit stehen wieder n − 1 Autos auf P , von denen wieder nach Induktionsvoraussetzung entweder alle rot sind oder keines. Das zeigt, dass a genau dann rot ist, wenn es die cj (j = 1, . . .) sind und damit auch b ist. Also sind die n Autos a, b und cj entweder alle rot oder nichtrot. Das war zu zeigen.

Zur L¨ osung. Die Aussage, nennen wir sie A(n), ist falsch f¨ur n ≥ 2. Der Fehler liegt im Induktionsschluss A(n − 1) ⇒ A(n), der nur f¨ur n ≥ 3 funktioniert: Um die Farben von a und b zu vergleichen, mu...