Universität des Saarlandes

Fachbereich 9, Mathematik Prof. Dr. R. Berger

�

0. Übung zur Linearen Algebra I, WS 1998/99

Zur nächsten Aufgabe: Fibonacci (ca 1180-1250) war der bedeutenste europäische Mathematiker des hohen Mittelalters. Er war ein weitgereister Kaufmann, der durch seine Reisen in die arabischen Länder mit den Errungenschaften der indisch-arabischen Mathematik in Kontakt kam und diese in seinem Buch liber abaci veröffentlichte. Seit seinem Werk wird das arabische Zahlsystem in Westeuropa regelmäßig benutzt. Fibonacci war während dreier Jahrhunderte der bedeutenste Mathematiker Europas. Eine seiner Fragestellungen hat auch heute noch große Bedeutung:

Aufgabe 1: (0 Punkte)

Jemand sperrte ein Kaninchenpaar in ein Gelände ein, das auf allen Seiten von Mauern umgeben war; er wollte herausbekommen, wie viele Kaninchenpaare aus diesem einen Paar in einem Jahre hervorgingen. Bei den Kaninchen ist es nun so, daß sie jeden Monat ein neues Paar in die Welt setzen; und damit fangen sie an, sobald sie zwei Monate alt sind. Das erwähnte erste Paar beginnt gleich mit der Fortpflanzung.

Wie viele Kaninchenpaare entstehen in einem Jahr aus einem Kaninchenpaar?

Modern formuliert würde dies bedeuten, daß es zu Anfang des ersten Monats F_{1} = 1 Kaninchenpaar gibt. Setzen wir voraus, daß es nach Beginn der Fortpflanzung einen Monat dauert bis das Weibchen ein neues Kaninchenpaar wirft, so gibt es zu Beginn des zweiten Monats F_{2} = 2 Kaninchenpaare, usw. Wie viele Kaninchenpaare F_{13} gibt es also nach Ablauf eines Jahres? Nimm an, daß F_{0} := 1 gilt. Versuche ein Bildungsgesetz für die F_{n} zu finden!

Zeige ferner, daß für natürliche Zahlen n und m die folgenden Aussagen gelten:

(i) F_{0} + F_{1} + … + F_{n} = F_{n+2} − 1
(ii) F_{n}^{2} − F_{n−1}F_{n+1} = (−1)^{n}, für n ≥ 1
(iii) F_{m+n} = F_{m−2}F_{n} + F_{m−1}F_{n+1}, für m ≥ 2, n ≥ 0
(iv) F_{n} = ^{\frac{(^{\frac{1+\sqrt{5}}{2}} )^{n+1}−(^{\frac{1−\sqrt{5}}{2}} )^{n+1}}{\sqrt{5}}}

Hinweis: Benutze zum Beweis vollständige Induktion.

Eine Anwendung der Fibonacci-Zahlen, werden wir später bei der Besprechung des Euklidschen Algorithmus sehen.

Aufgabe 2: (0 Punkte)

Eine Abbildung φ : X → Y zwischen zwei Mengen X und Y heißt genau dann injektiv, wenn für alle x_{1}, x_{2} ∈ X aus φ(x_{1}) = φ(x_{2}) bereits x_{1} = x_{2} folgt. Sie heißt surjektiv, wenn es zu jedem y ∈ Y ein x ∈ X mit φ(x) = y gibt.

Zeige für die beiden Abbildungen f : A → B und g : B → C die folgenden Eigenschaften:

(i) f, g injektiv ⇒ g ∘ f injektiv.
(ii) f, g surjektiv ⇒ g ∘ f surjektiv.
(iii) g ∘ f injektiv ⇒ f injektiv, aber nicht g injektiv.
(iv) g ∘ f surjektiv ⇒ g surjektiv, aber nicht f surjektiv.

Aufgabe 3: (0 Punkte)

Eine Abbildung f : X → Y zwischen zwei nichtleere Mengen heißt bijektiv (oder eineindeutig), wenn sie sowohl surjektiv als auch injektiv ist.

Es gibt auch eine andere Möglichkeit injektiv, surjektiv und bijektiv zu definieren (siehe Vorlesung). In den nachfolgenden Teilaufgaben zeigst Du, daß diese Definitionen äquivalent sind. Die hier benutzte Abbildung id_{X} : X → X : x↦x ist die Identität auf X.

(i) f ist genau dann injektiv, wenn es eine Abbildung g : Y → X gibt, so daß g ∘ f = id_{X} gilt.
(ii) f ist genau dann surjektiv, wenn es eine Abbildung g : Y → X gibt, so daß f ∘ g = id_{Y} gilt.
(iii) f ist genau dann bijektiv, wenn es eine Abbildung g : Y → X gibt, so daß f ∘ g = id_{Y} und
g ∘ f = id_{X} gelten.

Zur nächsten Aufgabe: Der Begiff der Unendlichkeit ist problematisch und dem ’gesunden Menschenverstand’ nicht ohne weiteres leicht zugänglich, da sich dort Dinge ereignen, die im Endlichen nicht geschehen können. Auf dem nächsten Aufgabenblatt werden wir sehen, wie man mit Hilfe bijektiver Abbildungen ein wenig ”Ordnung schaffen” kann. Als Vorbereitung dient die nachfolgende ”humoristische” Aufgabe.

Aufgabe 4: (0 Punkte)

Stelle Dir vor, Du bist EmpfangschefIn eines Hotels mit unendlich vielen Zimmern, die alle ein Bett enthalten, und deren Zimmernummern von 1 bis unendlich gehen. Du bist in der glücklichen Lage, alle Zimmer vermietet zu haben. Plötzlich geschieht folgendes:

(a) Nachts kommt ein Gast und begehrt ein Zimmer. Was tust Du?

(b) Etwas später kommt ein Bus mit unendlich vielen Gästen. Was machst Du nun?

Diese Aufgaben sind als ’Aufwärmübungen’ gedacht und müssen noch nicht abgegeben werden!! Sie werden in der Übungsgruppe nächste Woche besprochen.

Heute, Freitag 23. Oktober 1998, ist der letzte Tag, an dem Ihr Euch in eine der Übungsgruppen einschreiben könnt. Nächste Woche muß jedeR in der Übung erscheinen, welche er/sie sich heraussucht. Dort wird gegebenfalls die Gruppengröße verringert. Wer nur zu einem einzigen Zeitpunkt in eine Übungsgruppe gehen kann, soll auf alle Fälle dorthin gehen, auch wenn die Liste bereits voll ist. Irgendeine Lösung wird sich schon finden lassen. Wer zu keinem Übungstermin Zeit hat, sollte sich bei Holger Cröni, Raum 309 melden.

Informationen zu den Übungen: Es gibt zwei Klausuren zur Vorlesung, die erste am Samstag, 19.Dezember 1998, die zweite am Samstag, 20. Februar 1999; jeweils von 9 bis 13 Uhr. Außerdem findet für diejenigen, welche in einer Klausur durchgefallen sind eine Nachklausur in der ersten Aprilhälfte statt. Um einen Schein zu erhalten benötigt man:

• bestehen von zwei Klausuren

• erreichen von 40% der Punkte in den Übungen

• vorrechnen in den Übungsgruppen

• Mitarbeit in den Übungsgruppen

• häufige Anwesenheit in den Übungsgruppen

Die letzten drei Punkte sind eigentlich selbstverständlich und alle, welche die Klausur bestehen wollen, sollten von selbst darauf erpicht sein, in den Übungen aktiv zu sein. Nur wer 40% der Punkt aus den Übungen hat wird zur Klausur zugelassen!! Alle Informationen zum Ablauf der Übungen sind auf der Homepage der AG-Berger unter

http://www.math.uni-sb.de/~agberger/ag-berger.html zu finden. Dort wird es auch alle Übungs-

aufgaben zum Herunterladen geben.

Weitere Informationen und Antworten auf Fragen wird es nächste Woche in den Übungen geben.