2. ÜBUNG ZUR VORLESUNG „MATHEMATIK FÜR INFORMATIKER I“ IM WINTERSEMESTER 1999/2000

PROF. DR. BERENDT CARSTEN SCHULTZ

Information. Um die Verwirrung zu beenden, geben wir hier noch einmal kurz Orte und Zeiten aller Tutorien an. Carsten: Do 14–16 A2–6 032; Clemens: Mi 12– 14 T9 049, Mi 14–16 T9 039, Do 12–14 T9 039; Diana: Fr 14–16, T9 039; Stephan: Do 14–16 A2-6 025/026, Fr 8–10 T9 055.

Aufgabe 4. Es sei n eine natürliche Zahl. Auf der Menge der ganzen Zahlen ℤ sei die Relation ∼ durch

r ∼ s : ⟺ r − s ist ein ganzzahliges Vielfaches von n

definiert.

(i) Zeige, dass dies eine Äquivalenzrelation ist. (ii) Wie groß ist die Zahl der Äquivalenzklassen?

Aufgabe 5. Zeige durch vollständige Induktion, dass für alle natürlichen Zahlen n

\frac{2 n}{3} + \frac{n^{2}}{4} − \frac{n^{3}}{6} + \frac{n^{4}}{4}

eine ganze Zahl ist.

Aufgabe 6. Ist der folgende Beweis korrekt? Wenn nicht, wo liegt der Fehler? Proposition. Alle natürlichen Zahlen sind ungerade.

Beweis. Wir zeigen die Aussage „für alle n ∈ ℕ gilt, dass alle natürlichen Zahlen, die kleiner oder gleich n sind, ungerade sind“ durch Induktion über n. Induktionsanfang für n = 1: Die Aussage ist für n = 1 wahr,

da 1 ungerade ist. Induktionsschritt von n nach n + 1: Wir nehmen an, die Aussage sei für n wahr. Dann sind alle natürlichen Zahlen, die kleiner oder gleich n sind, ungerade, insbesondere also n − 1. Nun ist n + 1 = (n − 1) + 2 und damit ist n + 1 auch ungerade. Also sind alle natürlichen Zahlen, die kleiner oder gleich n + 1 sind, ungerade.

□

Abgabe: am 10. 11. 1999 in der Vorlesung.