Musterlösung zur 0.Übung  Seite 1

Universität des Saarlandes

Fachbereich 9, Mathematik Prof. Dr. R. Berger

�

Musterlösung zur 0. Übung der Linearen Algebra I, WS 1998/99

Lösung zur Aufgabe 1:

Zu Beginn des ersten Monats gibt es ein Kaninchenpaar. Da dieses sofort mit der Vermehrung beginnt, wirft es im zweiten Monat ein Nachkommenpaar, so daß es zwei Kaninchenpaare gibt. Im zwölften gibt es also F_{12} = 233 und nach Ablauf des Jahres F_{13} = 377. Im einzelnen ergibt sich 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 Kaninchenpaare. Das Bildungsgesetz lautet F_{n+2} := F_{n+1} + F_{n} für n ≥ 0 und F_{0} := 0. Die Beweise der Aussagen (i)-(iv) erfolgen durch vollständige Induktion

(i) Induktionsanfang n = 0: Es gilt F_{0} = F_{2} − F_{1} (1 = 2 − 1). Induktionsschritt n → n + 1: Die Aussage sei bereits für n gezeigt, d.h. es gilt F_{0} + F_{1} + … + F_{n} = F_{n+2} − 1. Dann gilt auch

(F_{0} + F_{1} + … + F_{n}) + F_{n+1} = (F_{n+2} − 1) + F_{n+1}, Assoziativität
= (F_{n+2} + F_{n+1}) − 1, da F_{n+3} = F_{n+2} + F n + 1
= F_{n+3} − 1
= F_{(n+1)+2} − 1.

(ii) Induktionsanfang n = 1: Es gilt F_{1}^{2} − F_{0}F_{2} = 1^{2} − 1 · 2 = (−1)^{1} Induktionsschritt n → n + 1:

F_{n+1}^{2} − F_{n}F_{n+2} = F_{n+1}^{2} − F_{n}(F_{n} − F_{n+1}), da F_{n+2} = F_{n+1} + F n
= F_{n+1}(F_{n+1} − F_{n}) − F_{n}^{2}
= F_{n+1}F_{n−1} − F_{n}^{2},  da F_{n+1} − F_{n} = (F_{n} + F_{n−1}) − F_{n} = F_{n−1}
= (−1)(F_{n}^{2} − F_{n+1}F_{n−1})
= (−1) · (−1)^{n},  da für die 2. Klammer die IV gilt
= (−1)^{n+1}

(iii) Induktionsanfang n = 0: Wegen F_{m} = F_{m−2} · 1 + F_{m−1} · 1 gilt F_{m} = F_{m−2}F_{0} + F_{m−1}F_{1} ∀ m. Induktionsschritt n → n + 1: Wir müssen F_{m+n+1} − (F_{m−2}F_{n+1} + F_{m−1}F_{n+2}) = 0 zeigen. Betrachte

F_{(m+1)+n} − (F_{m−2}F_{n+1} + F_{m−1}F_{n+2})

= (F_{m−1}F_{n} + F_{m}F_{n+1}) − (F_{m−2}F_{n+1} + F_{m−1}F_{n+2})
= F_{m−1}(F_{n} − F_{n+2}) + F_{n+1}(F_{m} − F_{m−2})
= F_{m−1}(−F_{n+1}) + F_{n+1}(F_{m−1}) = 0

(iv) Induktionsanfang n = 0: Es gilt F_{0} = ^{\frac{(^{\frac{1+\sqrt{5}}{2}} )−(^{\frac{1−\sqrt{5}}{2}} )}{\sqrt{5}}} = 1.

Induktionsanfang n = 1: Es gilt F_{1} = ^{\frac{(^{\frac{1+\sqrt{5}}{2}} )^{2}−(^{\frac{1−\sqrt{5}}{2}} )^{2}}{\sqrt{5}}} = \frac{1}{2^{2}\sqrt{5}} ((1 + 2\sqrt{5} + 5) − (1 − 2\sqrt{5} + 5)) = \frac{1}{4\sqrt{5}} · (4\sqrt{5}) = 1

Induktionsschritt n → n + 1 für n ≥ 2: Die Lösungen der quadratischen Gleichungen q^{2} = q + 1 sind a = \frac{1+\sqrt{5}}{2} und b = \frac{1−\sqrt{5}}{2}. Wegen n ≥ 2 gilt

F_{n+1} = F_{n} + F_{n−1},  nach Induktionsvoraussetzung ist dies
= \frac{a^{n+1}−b^{n+1}}{\sqrt{5}} + \frac{a^{n}−b^{n}}{\sqrt{5}}
= \frac{1}{\sqrt{5}} ((a^{n+1} + a^{n}) − (b^{n+1} + b^{n}))
= \frac{1}{\sqrt{5}} (a^{n}(a + 1) − b^{n}(b + 1)) ,  es ist a^{2} = a + 1
= \frac{1}{\sqrt{5}} (a^{n} · a^{2} − b^{n} · b^{2})
= \frac{1}{\sqrt{5}} (a^{n+2} − b^{n+2})
= \frac{a^{(n+1)+1}−b^{(n+1)+1}}{\sqrt{5}}

Lösung zur Aufgabe 2:

(i) Seien a_{1}, a_{2} ∈ A mit (g ∘ f)(a_{1}) = (g ∘ f)(a_{2}). Umgeschrieben ist dies g(f(a_{1})) = g(f(a_{2})). Aus der Injektivität der Abbildung g folgt nun f(a_{1}) = f(a_{2}), woraus wegen der Injektivität von f das geforderte a_{1} = a_{2} folgt. Also ist g ∘ f injektiv.

(ii) Sei c ∈ C beliebig. Da g surjektiv ist, gilt ∃ b ∈ B : g(b) = c und da f surjektiv ist, gilt ∃ a ∈ A : f(a) = b. Also ist (g ∘ f)(a) = c und g ∘ f surjektiv.

(iii) a) Beweis durch Widerspruch. Angenommen, f ist nicht injektiv. Dann gilt: ∃ a_{1} ≠ a_{2} ∈ A : f(a_{1}) = f(a_{2}). Ferner gilt (g ∘ f)(a_{1}) = (g ∘ f)(a_{2}) ⇒ (g ∘ f) nicht injektiv. Widerspruch zur Voraussetzung.

b) g muß nicht zwingend injektiv sein. Beweis durch Beispiel: Seien A = {1}, B = {1, 2, 3}, C = {1} und f : A → B : 1↦1, g : B → C : 1, 2, 3↦1.

(iv) a) Sei c ∈ C beliebig. Da g ∘ f surjektiv ist, gilt: ∃ a ∈ A : (g ∘ f)(a) = c, d.h. ∃ b ∈ B : b = f(a) und g(b) = c. Also ist g surjektiv.

b) Daß f nicht zwingend surjektiv sein muß, sieht man wieder an dem Beipiel in (iii).

Lösung zur Aufgabe 3:

Die Idee besteht darin, die Funktion g mit den gewünschten Eigenschaften zu konstruieren. Man verdeutliche sich diese Beweise durch Bilder!

(i) ”⇒”: Sei f injektiv. Dann gibt es zu jedem y ∈ f(X) genau ein x ∈ X mit f(x) = y, und wir definieren g(y) := x. Ist x_{0} ∈ X beliebig, so definieren wir weiter g(y) = x_{0} für alle y ∈ Y ∖ f(X). Das ergibt eine Abbildung g : Y → X mit g ∘ f = id_{X}.

”⇐”: Ist umgekehrt g : Y → X mit g ∘ f = id_{X} gegeben, und ist f(x) = f(x′) für x, x′ ∈ X, so ist

x = id_{X}(x) = g(f(x)) = g(f(x′)) = id_{X}(x′) = x′.

Also ist f injektiv.

(ii) ”⇒”: Sei f surjektiv. Zu jedem y ∈ Y wählen wir ein festes x ∈ X mit f(x) = y und setzen g(y) := x. Die so erklärte Abbildung g : Y → X hat die Eigenschaft f ∘ g = id_{Y}.

”⇐”: Ist umgekehrt g : Y → X mit f ∘ g = id_{Y} gegeben, und ist y ∈ Y, so ist y = f(g(y)), also Bild von g(y), und f ist surjektiv.

(iii) ”⇒”: Sei f bijektiv. Dann erfüllt g := f^{−1} die beiden Gleichungen.

”⇐”: Ist umgekehrt g : Y → X mit f ∘ g = id_{Y} und g ∘ f = id_{X} gegeben, so ist f nach (i) und (ii) bijektiv, und es gilt g = f^{−1}.

Lösung zur Aufgabe 4:

(a) Ich bitte den ersten Gast, in das zweite Zimmer zu ziehen, den Gast aus dem zweiten Zimmer ins dritte zu ziehen, den Gast aus dem dritten … Auf diese Weise ist das erste Zimmer frei geworden und der neue Gast kann dort einziehen.

(b) Ich unterschlage hier, daß es verschiedene Arten von Unendlichkeit gibt und gehe nur von abzählbar unendlich aus (s. nächstes Übungsblatt).

Ich bitte den Gast aus dem ersten Zimmer ins zweite zu ziehen, den aus dem zweiten ins vierte, den aus dem dritten ins sechste, . . .. Auf diese Weise sind alle Zimmer mit ungeraden Nummer frei und das sind bekanntlich unendlich viele freie Zimmer.