Mathe II für Informatiker Sommersemester 05 Walter Oevel 3. 5. 2005

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

Lösungen von ∗-Aufgaben sind per Web-Formular unter http://math-www.upb.de/~walter (⟶ Lehre SS 05 ⟶ Übungen) bis spätestens Do, 12.5.05, abzuliefern. Lösungen von ∗∗-Aufgaben sind schriftlich abzugeben. Sie werden zu Beginn der Vorlesung am Mi, 11.5.05 eingesammelt.

Aufgabe 22: (Folgen, Grenzwerte. Einfacher Beweis.) Sei (z_{n}) eine konvergente komplexe Folge. Zeige, dass die Menge {|z_{n}|, n ∈ ℕ} nach oben beschränkt ist.

Musterlösung: Sei z^{∗} der Grenzwert. Zu jedem ϵ > 0 existiert ein N(ϵ), so dass |z_{n} − z^{∗}| ≤ ϵ gilt für alle n ≥ N(ϵ), also |z_{n}| ≤ |z^{∗}| + ϵ. Speziell für ϵ = 1 folgt also

|z_{n}| ≤ |z^{∗}| + 1 für alle n ≥ N(1).

Der ”Folgenschwanz“ ab N(1) ist damit beschränkt. Der Folgenanfang bis N(1) besteht nur aus endlich vielen Werten, deren Beträge ein Maximum haben. Eine obere Schranke für |z_{n}| ist damit durch

max(max {|z_{n}|; 1 ≤ n < N(1)}, |z^{∗}| + 1}

gegeben.

Aufgabe 23: (Folgen, Grenzwerte. Einfacher Beweis.) Die komplexe Folge (z_{n}) konvergiere gegen z^{∗}. Zeige, dass die komplex-konjugierte Folge (\overline{z_{n}}) gegen \overline{z^{∗}} konvergiert.

Musterlösung: Es gilt |z| = \sqrt{z · \overline{z}} = |\overline{z}|. Zu ϵ > 0 existiert ein N(ϵ), so dass |z_{n} − z^{∗}| ≤ ϵ gilt für alle n ≥ N(ϵ). Alle dieses Folgenglieder erfüllen auch

|\overline{z_{n}} − \overline{z^{∗}}| = |\overline{z_{n} − z^{∗}}| = |z_{n} − z^{∗}| ≤ ϵ,

d.h., (\overline{z_{n}}) konvergiert gegen \overline{z^{∗}}.

Aufgabe 24: (Folgen, Grenzwerte. Beweise.) Seien (x_{n}) und (y_{n}) konvergente reelle Folgen mit den Grenzwerten x^{∗} bzw. y^{∗}.

a) Es gelte x_{n} ≤ y_{n} für alle Indizes. Zeige: x^{∗} ≤ y^{∗}. (Indirekter Beweis.)

b) Es gelte x_{n} < y_{n} für alle Indizes. Gilt immer x^{∗} < y^{∗}? (Finde ein Gegenbeispiel.)

Musterlösung:

a) Angenommen, es gilt x^{∗} > y^{∗}. Betrachte ϵ = (x^{∗} − y^{∗})/3 > 0. Zu diesem ϵ gibt es Folgenglieder x_{n} bzw. y_{n} mit

|x_{n} − x^{∗}| ≤ ϵ, |y_{n} − y^{∗}| ≤ ϵ,

also

x^{∗} − ϵ ≤ x_{n} ≤ y_{n} ≤ y^{∗} + ϵ ⇒ x^{∗} − y^{∗} ≤ 2 · ϵ.

Für das konkrete ϵ = (x^{∗} − y^{∗})/3 folgt der Widerspruch

x^{∗} − y^{∗} ≤ \frac{2}{3} · (x^{∗} − y^{∗}).

b) Gegenbeispiel: x_{n} = 1, y_{n} = 1 + 1/n mit x_{n} < y_{n} für alle n, aber lim_{n→∞} x_{n} = 1 = lim_{n→∞} y_{n}.

Aufgabe 25: (Folgen, Grenzwerte. Einfacher Beweis) Sie (z_{n}) eine konvergente Folge. Zeige durch einen formal sauberen Beweis, dass für jedes (fixierte) k ∈ ℕ die ”verschobenen“ Folgen (z_{n+k}) gegen den selben Grenzwert konvergieren.

Musterlösung: (z_{n}) → z^{∗} bedeutet, dass es zu jedem ϵ > 0 ein N(ϵ) gibt, so dass |z_{n} − z^{∗}| ≤ ϵ gilt für alle Indizes n ≥ N(ϵ). Betrachte nun (z_{n+k}). Zu gegebenem ϵ > 0 setze N^{(k)}(ϵ) = N(ϵ) − k. Dann gilt für alle n ≥ N^{(k)}(ϵ), also n + k ≥ N(ϵ):

|z_{n+k} − z^{∗}| ≤ ϵ.

Dies ist die Konvergenz von (z_{n+k}) gegen z^{∗}.

Aufgabe 26: (Folgen, Grenzwerte)

Bestimme lim_{n→∞} \frac{2^{n}}{n!} .

Musterlösung: Es gilt

0 < \frac{2^{n}}{n!} = \frac{2 · 2 · \overbrace{2 · 2 . . . · 2}^{n−2}}{1 · 2 · \underbrace{3 · 4 . . . · n}_{n−2}} < \frac{2 · 2 · \overbrace{2 · 2 . . . · 2}^{n−2}}{1 · 2 · \underbrace{3 · 3 . . . · 3}_{n−2}} = 2 · (\frac{2}{3})^{n−2} = \frac{9}{2} · (\frac{2}{3})^{n}.

Bekanntlich bildet (2/3)^{n} eine Nullfolge (Beispiel 2.10 der Vorlesung). Per Intervallschachtelung (Satz

2.17 der Vorlesung) folgt lim_{n→∞} \frac{2^{n}}{n!} = 0.

Aufgabe 27∗∗: (Folgen, Grenzwerte. Intervallschachtelung. 10 Bonuspunkte) Diese Aufgabe kann schriftlich bearbeitet werden. Bearbeitungen werden zu Beginn der Vorlesung am Mi, 11.5.05, eingesammelt.

Bestimme lim_{n→∞} ^{n} \sqrt{3^{n} + 5^{n}}.

Anleitung: Satz 2.17. Es gilt 5^{n} < 3^{n} + 5^{n} < 2 · 5^{n}.

Musterlösung: Der Anleitung folgend:

5^{n} < 3^{n} + 5^{n} < 2 · 5^{n} ⇒ 5 < ^{n} \sqrt{3^{n} + 5^{n}} < ^{n} \sqrt{2} · 5.

Bekanntlich konvergiert ^{n} \sqrt{2} gegen 1 (Beispiel 2.19 der Vorlesung). Per Intervallschachtelung (Satz 2.17 der Vorlesung) folgt lim_{n→∞} ^{n} \sqrt{3^{n} + 5^{n}} = 5.

Aufgabe 28*: (Intervallschachtelung, 10 Bonuspunkte) Seien M_{1}, M_{2} positive Zahlen (die von hex zufällig gewählt werden). Bestimme:

lim_{n→∞} ^{n} \sqrt{M_{1}^{n} + M_{2}^{n}}.

Anleitung: Siehe Aufgabe 27.

Musterlösung: Gilt M_{1} ≥ M_{2}, so folgt analog zu Aufgabe 27

M_{1}^{n} ≤ M_{1}^{n} + M_{2}^{n} ≤ 2 · M_{1}^{n}

und der Grenzwert ergibt sich analog zu Aufgabe 27 als M_{1}. Gilt M_{1} ≤ M_{2}, so folgt analog zu Aufgabe 27

M_{2}^{n} ≤ M_{1}^{n} + M_{2}^{n} ≤ 2 · M_{2}^{n},

und der Grenzwert ergibt sich analog zu Aufgabe 27 als M_{2}. Zusammengefasst ist der Grenzwert

lim_{n→∞} ^{n} \sqrt{M_{1}^{n} + M_{2}^{n}} = max(M_{1}, M_{2}).

Aufgabe 29∗∗: (Konvergenz monotoner Folgen, 10 Bonuspunkte) Diese Aufgabe kann schriftlich bearbeitet werden. Bearbeitungen werden zu Beginn der Vorlesung am Mi, 11.5.05, eingesammelt.

Betrachte die durch x_{n+1} = \sqrt{1 + x_{n}}, x_{1} = 0 definierte Folge.

a) Zeige, dass (x_{n}) streng monoton wachsend ist.

b) Zeige per Induktion: 0 ≤ x_{n} < 2 für alle n ∈ ℕ.

c) Bestimme den Grenzwert von (x_{n}).

Musterlösung:

a) Behauptung: x_{n} < x_{n+1}. Induktionsstart: x_{1} = 0, x_{2} = 1, also x_{1} < x_{2}. Induktionsschritt n−1 → n: Sei x_{n} > x_{n−1}. Es folgt

x_{n+1} = \sqrt{1 + x_{n}} > \sqrt{1 + x_{n−1}} = x_{n}.

b) Behauptung: x_{n} < 2. Induktionsstart: x_{1} = 0 < 2. Induktionsschritt: Sei x_{n} < 2. Es folgt

x_{n+1} = \sqrt{1 + x_{n}} < \sqrt{1 + 2} = \sqrt{3} < 2.

c) Sei x^{∗} der Grenzwert. Es muß gelten:

lim_{n→∞} x_{n+1} = x^{∗} = lim_{n→∞} \sqrt{1 + x_{n}} = \sqrt{1 + lim_{n→∞} x_{n}} = \sqrt{1 + x^{∗}}

⇒ (x^{∗})^{2} = 1 + x^{∗} ⇒ x^{∗} = \frac{1 ± \sqrt{5}}{2}.

Nur der positive Wert x^{∗} = \frac{1+\sqrt{5}}{2} kommt als Grenzwert in Frage.

Aufgabe 30*: (Intervallschachtelung, 10 Bonuspunkte) Sei M eine Zahl (die von hex zufällig gewählt wird). Betrachte die durch x_{n+1} = \sqrt{M + 2 · x_{n}}, x_{1} = 1 definierte Folge. Ermittle eine obere Schranke für die Folgenglieder und berechne den Grenzwert. Anleitung: siehe Aufgabe 29.

Musterlösung: Analog zu Aufgabe 29.a) ergibt sich die Monotonie unmittelbar durch Induktion. Jede Konstante K, die größer als der berechnete Grenzwert ist, ist eine obere Schranke (wegen der Monotonie). In der Tat liefert Induktion sofort den Beweis, dass z.B. M (> 1 + \sqrt{1 + M}) für alle alle von hex gewählten Zahlen M eine obere Schranke ist:

x_{n} ≤ M ⇒ x_{n+1} = \sqrt{M + 2 · x_{n}} ≤ \sqrt{M + 2 · M} = \sqrt{3 · M} ≤ M,

da alle von hex gewählten Zahlen M größer als 3 sind, also 3 · M ≤ M^{2} gilt. Der Grenzwert x^{∗} ergibt sich aus der Gleichung

x^{∗} = \sqrt{M + 2 · x^{∗}} ⇒ (x^{∗})^{2} − 2 · x^{∗} − M = 0 ⇒ x^{∗} = 1 ± \sqrt{1 + M}.

Nur der positive Wert 1 + \sqrt{1 + M} kommt als Grenzwert in Frage.

Aufgabe 31: (Die Fibonacci-Zahlen) Die Fibonacci-Folge (F_{n}) ist durch

F_{n+1} = F_{n} + F_{n−1} mit F_{0} = 0, F_{1} = 1

definiert. Betrachte die Folge x_{n} = F_{n+1}/F_{n}, n ∈ ℕ. Diese Folge konvergiert.

a) Ermittle eine Gleichung für den Grenzwert von (x_{n}) und berechne ihn. b) Berechne die ersten 25 Werte x_{1}, …, x_{25}. Wie genau approximiert (rein experimentell)

x_{25} den Grenzwert?

c) In welcher Größenordnung liegt F_{10^{7}} (wieviele Dezimalstellen hat diese Zahl ungefähr)?

Eine grobe Abschätzung soll hier ausreichen. Anleitung zu c): Man versuche erst gar nicht, F_{10^{7}} mittels MuPADs numlib::fibonacci exakt zu berechnen. Verwende F_{n} = x_{n−1} · F_{n−1} = x_{n−1} · x_{n−2} · F_{n−2} = … zusammen mit a) für eine grobe Abschätzung.

Musterlösung:

a) Aus der Rekursion der Fibonacci-Zahlen folgt

F_{n+1} = F_{n} + F_{n−1} ⇒ \frac{F_{n+1}}{F_{n}} = 1 + \frac{F_{n−1}}{F_{n}} ⇒ x_{n} = 1 + \frac{1}{x_{n−1}} .

Für x^{∗} = lim_{n} x_{n} folgt ”wie üblich“ die Gleichung

x^{∗} = 1 + \frac{1}{x^{∗}} ⇒ (x^{∗})^{2} = x^{∗} + 1 ⇒ x^{∗} = \frac{1}{2} ± \frac{\sqrt{5}}{2}.

Nur der positive Wert x^{∗} = \frac{1+\sqrt{5}}{2} kommt als Grenzwert in Frage. b)

>> x:= n -> numlib::fibonacci(n+1)/numlib::fibonacci(n):
>> float(x(n)) $ n=1..25
1.0, 2.0, 1.5, 1.666666667, 1.6, 1.625, 1.615384615,
   1.619047619, 1.617647059, 1.618181818, 1.617977528,
   1.618055556, 1.618025751, 1.618037135, 1.618032787,
   1.618034448, 1.618033813, 1.618034056, 1.618033963,
   1.618033999, 1.618033985, 1.61803399, 1.618033988,
   1.618033989, 1.618033989

Die ersten 10 Stellen von x_{25} scheinen schon stabil geworden zu sein und mit denen des Grenzwerts übereinzustimmen.

c) Es gilt

F_{n} = x_{n−1} · F_{n−1} = x_{n−1} · x_{n−2} · F_{n−2} = … = \underbrace{x_{n−1} · x_{n−2} · . . . · x_{k}}_{n−k} ·F_{k}

mit beliebigem k ∈ {1, 2, 3, …, n − 1}. Da (x_{n}) einigermaßen schnell gegen den Grenzwert x^{∗} strebt, kann man x^{∗} ≈ x_{n} ≈ x_{n−1} ≈ … setzen und es folgt

F_{n} ≈ (x^{∗})^{n−k} · F_{k} für jedes ”hinreichend große“ k, für das die Näherung x_{k} ≈ x_{k+1} ≈ … ≈ x_{n−1} ≈ x^{∗} gerechtfertigt ist. Wählen wir z.B. k = 25 (die betrachteten Folgenglieder x_{25}, x_{26}, … scheinen nach b) alle den Grenzwert auf mindestens 10 Dezimalstellen genau zu approximieren), so erhalten wir:

>> x:= float((1 + sqrt(5))/2):
>> k:= 25:
>> x^(10^7 - k)*numlib::fibonacci(k)
                      1.129834378e2089876

Also: F_{10^{7}} hat über 2 Millionen Dezimalstellen.