Mathe II für Informatiker Sommersemester 02 Walter Oevel 16. 5. 2002

Ü b u n g s b l a t t 5

Mit ∗ gekennzeichnete Aufgaben können zum Sammeln von Bonuspunkten verwendet werden. Lösungen sind per Web-Formular unter http://math-www.upb.de/~walter (⟶ Lehre SS 02 ⟶ Übungen) bis spätestens Do, 23.5.02, abzuliefern.

Aufgabe 32: (Folgen, Konvergenz. Das geometrisch-arithmetische Mittel) Sei 0 < x < y.

a) Zeige x < \sqrt{x · y} < \frac{x + y}{2} < y.

Definiere x_{1} = x, y_{1} = y und dann rekursiv x_{n+1} = \sqrt{x_{n} · y_{n}}, y_{n+1} = \frac{x_{n} + y_{n}}{2} .

b) Zeige, dass (x_{n}) streng monoton steigend und dass (y_{n}) streng monoton fallend ist.

c) Zeige, dass (y_{n} − x_{n}) eine Nullfolge ist.

d) Folgere, dass (x_{n}) und (y_{n}) gegen den selben Grenzwert konvergieren.

Man nennt diesen Grenzwert das ”geometrisch-arithmetische Mittel“ von x und y.

e) Berechne für x = 1, y = 2 die ersten 5 Intervalle [x_{n}, y_{n}]. Wie schnell nehmen die Intervalllängen y_{n} − x_{n} ab?

f) (Etwas anspruchsvoller) Sei x ≥ 1.

i) Zeige: \sqrt{x_{n}} + \sqrt{y_{n}} ≥ 1 für alle n,

ii) Folgere: \sqrt{y_{n}} − \sqrt{x_{n}} ≤ y_{n} − x_{n} für alle n,

iii) Folgere: y_{n+1} − x_{n+1} ≤ \frac{1}{2} · (y_{n} − x_{n})^{2}.

Wieso erklärt iii) die in e) beobachtete schnelle Konvergenz?

Aufgabe 33: (O–Kalkül) Zeige: für n → ∞ gilt

a) \frac{1}{n − 1} + \frac{1}{n + 1} − \frac{2}{n} = O(\frac{1}{n^{3}} ), b) \frac{1}{n − 1} + \frac{1}{n + 1} − \frac{2}{n} = \frac{2}{n^{3}} + O(\frac{1}{n^{5}} ).

Aufgabe 34: (O–Kalkül)

a) Zeige: wenn f(n) = o(g(n)) gilt, dann gilt auch f(n) = O(g(n)).

b) Sei k ∈ ℤ. Wenn f(n) = o(n^{k}) gilt, folgt dann automatisch f(n) = O(n^{k−1})?

c) Sei k ∈ ℤ. Wenn f(n) = o(n^{k}) gilt, folgt dann automatisch f(n) = o(n^{k+1})?

d) Seien k_{1}, k_{2} ∈ ℤ. Zeige O(n^{k_{1}}) · O(n^{k_{2}}) = O(n^{k_{1}+k_{2}}).

Aufgabe 35*: (Geometrische Reihen, 1 Bonuspunkt) Seien M_{1}, …, M_{7} die üblichen Ziffern der Matrikelnummer. Berechne

∑_{k=M_{6}}^{∞} (\frac{M_{1} + M_{3}}{2 · M_{1} + 3 · M_{3} + M_{4}} )^{(M_{1}−2)·k}.

Aufgabe 36: (Reihen, p-adische Darstellung) Sei p ∈ {2, 3, 4, …}. Mit der sogenannten ”p-adischen Darstellung“

b_{k} b_{k−1} … b_{1} b_{0} . b_{−1} b_{−2} b_{−3} …

ist die Zahl ∑_{j≤k} b_{j} · p^{j} gemeint, wobei b_{j} ∈ {0, 1, …, p − 1} die ”Ziffern zur Basis p“ genannt

werden. (Für p = 10 sind dies die wohlbekannten Dezimalziffern, für p = 2 die Binärziffern (Bits) b_{j} ∈ {0, 1}.)

a) Berechne die rationale Zahl, die im Binärsystem durch die periodische Entwicklung

1011 . 1100 \overline{10} (= 1011 . 1100 10 10 10 10 …)

gegeben ist.

b) (Erinnerung an die Mathe I) Gegeben sei eine reelle Zahl 0 < x < 1. Gib einen Algorithmus, an, welcher die Ziffern von x zur Basis p berechnet. Verwende als Hilfsmittel nur die sogenannte ”Gauss-Klammer“ ⌊y⌋ = die größte ganze Zahl ≤ y. (In einigen Hochsprachen steht diese Funktion z.B. als trunc zur Verfügung.)

Aufgabe 37*: (p-adische Darstellung. 1 Bonuspunkt) Seien M_{1}, …, M_{7} die üblichen Ziffern der Matrikelnummer. Welche rationale Zahl wird durch folgende periodische Hexadezimalzahl (Basis p = 16) dargestellt:

M_{1} M_{2} . M_{3} M_{4} \overline{M_{6} M_{7}} (= M_{1} M_{2} . M_{3} M_{4} M_{6} M_{7} M_{6} M_{7} M_{6} M_{7} …) ?

Anleitung: Aufgabe 36.

Aufgabe 38*: (p-adische Darstellung. 1 Bonuspunkt) Seien M_{1}, …, M_{7} die üblichen Ziffern der Matrikelnummer. Berechne die ersten 10 Ziffern b_{−1}, …, b_{−10} ∈ {0, 1, …, 6} zur Basis p = 7 von

\frac{1}{\sqrt{M_{1} + M_{2} + ⋯ + M_{7}}} = 0 . b_{−1} b_{−2} b_{−3} ….

Anleitung: Aufgabe 36.b) (MuPAD-Hilfsmittel: trunc. Für Schleifen siehe for, repeat oder while.) Mit der MuPAD-Funktion numlib::g adic kann das Ergebnis überprüft werden.