9. Folgen

Definition

Mathematisch können wir eine Folge deshalb als Abbildung $\mathbb{N} \to \mathbb{R}$ auffassen: Jeder Position wird eine Zahl zugeordnet. Die Abbildung $f: n \mapsto 2n$ generiert demnach die Folge der geraden Zahlen:

Die Schreibweise $f: n \mapsto f(n)$ ist für Folgen eher nicht gebräuchlich. Eher benutzt man die Indexschreibweise $f: n \mapsto f_n$. Meist aber einfach $(f_n)_{n\in\mathbb{N}}$ oder noch kürzer $(f_n)$. Die Klammern vermeiden Verwechslungen mit $f_n$, was das $n$-te Glied der Folge $(f_n)$ bezeichnet.

Alternative Darstellungsmöglichkeiten

Partialsummen

Oft ist es praktischer, nicht die Folgenglieder $f_n$ explizit aufzuschreiben, sondern die Differenz $s_n := f_n-f_{n-1}$ zwischen benachbarten Folgengliedern. Man spricht dann von einer Reihe mit Reihengliedern $(s_n)$ und den Partialsummen:

(Man beachte, dass sich aus der Definition für den Folgenanfang $f_1=s_1$ ergibt.)

Rekursiv

Speziell in der Informatik treten (bei Kostenanalysen) oft rekursiv definierte Folgen auf, bei denen jede Zahl $f_n$ nach einer festen Vorschrift aus dem Vorgänger $f_{n-1}$ (oder weiteren Vorgängern) berechnet wird. Wichtig: Festlegen der Anfangs(Start)-Werte, damit die Folge überhaupt eindeutig definiert ist. Einfaches Beispiel ist z.B. das Verdoppeln: Die Vorschrift $f_n = 2 f_{n-1}$ führt auf die Folge $1{,}2,4{,}8,16{,}32, \dots,$sofern man vorher festgelegt hat, dass $f_1 = 1$ sein soll.

Beispiel: Die Vorschrift $f_n = nf_{n-1}$, $f_1=1$ liefert dagegen die Folge $1{,}2,6{,}24, \dots$, also $f_n = n!.$

Beispiel: Eine typische Anwendung von Folgen in der Informatik: die Laufzeit eines Programms für verschiedene Eingaben; etwa die Folge $(a_n)$ der Anzahl der Vergleiche, die ein Sortierprogramm zum Sortieren von $n$ Zahlen höchstens durchführt (Insert-Sort).

Bei Laufzeitvergleichen ist insbesondere interessant, wie sich die Laufzeiten für immer größere $n$ verhalten. Wachsen? Fallen? Wie stark?

Entsprechend sind folgende Eigenschaften von Folgen von praktischer Bedeutung:

Monotonie von Folgen

Eine Folge heißt monoton wachsend, wenn jedes Element größer oder gleich seinem Vorgänger ist, also $f_n \ge f_{n-1}$ für jedes $n \ge 2$.

Folgen mit $f_n > f_{n-1}$ heißen streng monoton wachsend.

Eine Folge heißt entsprechend monoton fallend bzw. streng monoton fallend, wenn die Elemente kleiner werden, also $f_n \le f_{n-1}$ bzw. $f_n < f_{n-1}$.

Obere/ untere Schranken

Mindest- oder Maximallaufzeiten sind wichtig, daher sind wir an oberen/unteren Schranken für unsere Folgenelemente interessiert:

Gibt es eine Zahl $C\in\mathbb{R}$ mit $C \ge f_n$ für alle $n$, dann nennt man $C$ eine obere Schranke.

Alle Zahlen, die größer als $C$ sind, sind natürlich erst recht obere Schranken; am interessantesten ist daher eine kleinste obere Schranke, die heißt dann Supremum: $\sup f_n$.

Entsprechend heißt ein $c\in\mathbb{R}$ mit $c\le f_n$ für alle $n$ eine untere Schranke, besonders interessant ist hier eine größte untere Schranke, die heißt Infimum: $\inf f_n$.

Hat eine Folge sowohl eine obere als auch eine untere Schranke, dann nennt man sie beschränkt

.

Konvergenz und Divergenz

Bei Folgen (und mithin auch bei Reihen) interessiert oft, was mit den Folgengliedern $f_n$ im Grenzwert sehr großer $n$ passiert.

Der "gutmütige" Fall dabei ist, dass die Folge gegen eine Grenzwert $y$ konvergiert, d.h., dass für hinreichend großes $n$ alle Folgenglieder beliebig nahe an $y$ liegen:

Zur Erklärung: definiere die $\epsilon$-Umgebung einer Zahl $y\in\mathbb{R}$

"Beliebig nahe an $y$" heißt nun, dass für jedes (noch so kleine) $\epsilon>0$ die Folgenglieder ab einem $n_0(\epsilon)$ in $U_\epsilon(y)$ liegen.

Es dürfen also insbesondere nur endlich viele Folgenglieder außerhalb von $U_{\epsilon}$ liegen! Für kleineres $\epsilon$ muss man dann meist ein größeres $n_0(\epsilon)$ nehmen.

Konvergenz heißt also:

In diesem Fall heißt $y$ der Grenzwert der Folge: $y=\lim_{n\to\infty}f_n$.

Beispiele:

• $\displaystyle\lim_{n\to\infty} \frac{1}{n} = 0$ (wähle $n_0(\epsilon) := \lceil \frac{1}{\epsilon}\rceil +1$),

• $\displaystyle\lim_{n\to\infty} \frac{n+1}{n} = 1$ (umformen zu $1 + \frac{1}{n} \rightarrow 1$),

• $\displaystyle\lim_{n\to\infty} \frac{n+(-1)^n}{n} = 1\quad\left(\left|\frac{(-1)^n}{n}\right| = \frac{1}{n} \rightarrow 0 \right)$

Konvergenz durch monotone, beschränkte Folgen

Ein nützlicher Satz zur Konvergenz:

Häufungspunkte - limes superior und limes inferior

Die Folge $(f_n)$ mit $f_n := (-1)^n + \frac{1}{n}$ konvergiert nicht gegen einen Grenzwert, aber die Werte $1$ und $-1$ haben ähnliche Eigenschaften wie ein Grenzwert. In jeder Umgebung sind unendlich viele Folgenglieder enthalten, aber eben für beide Werte! Einen Wert mit dieser Eigenschaft (in jeder Umgebung sind unendlich viele Folgeglieder enthalten) nennt man Häufungspunkt der Folge.

Man beachte den Unterschied zwischen "nur endlich viele Folgenglieder sind außerhalb der Umgebung" (Grenzwert) und "unendlich viele Folgenglieder sind in der Umgebung" (Häufungspunkt).

Eine beschränkte Folge reeller Zahlen besitzt immer wenigstens einen Häufungspunkt. Beweis durch Intervallschachtelung: Man betrachtet das Intervall zwischen einer unteren und einer oberen Schranke, halbiert es, überlegt sich, dass in wenigstens einer Hälfte noch unendlich viele Folgenglieder liegen müssen, halbiert diese Hälfte, … Daher erzeugen wir auf diese Art und Weise eine geschachtelte Folge immer kleinerer Intervalle, deren Obergrenzen eine monoton fallende, beschränkte, also konvergente Folge bilden. Grenzwert dieser Folge ist ein Häufungspunkt!

Von besonderem Interesse bei beschränkten Folgen ist der größte Häufungspunkt, oder Limes superior der Folge. Dazu betrachten wir zunächst zu einer beschränkten Folge $(f_n)$ die Folge $(g_n)$ mit $g_n := \sup_{m\geq n} f_m.$ Wegen der Beschränktheit von $(f_n)$ ist auch $(g_n)$ beschränkt, weiter ist $(g_n)$ monoton fallend (warum?), mithin konvergent und der Grenzwert

ist der größte Wert, für den in jeder Umgebung unendlich viele $f_n$ liegen: der größte Häufungspunkt.

Zum Beweis sind zwei Eigenschaften zu zeigen:

• In jeder Umgebung liegen unendlich viele Folgenglieder.

• Kein größerer Wert hat diese Eigenschaft.

Dazu überlegen wir uns, dass für $C := \limsup x_n$ einer beschränkten Folge $(x_n)$ gilt, dass für jedes $\epsilon>0$ nur endlich viele $x_n$ größer als $C+\epsilon$ sind.

Wären unendlich viele Glieder größer als $C+\epsilon$, so könnte man daraus eine unendliche Folge definieren, mit Häufungspunkt.

Was passiert, wenn keine Konvergenz vorliegt? Divergenz:

In diesem Fall heißt die Folge divergent.

Formen der Divergenz

Es gibt zwei verschiedene Formen der Divergenz:

• Divergenz als "Konvergenz" gegen Unendlich ($+$ oder $-$):

• Divergenz durch mehr als einen Häufungspunkt: $f_n := (-1)^n$ ($-1$ und $1$) oder $g_n=n\cdot(-1)^n$ ($+^{\infty}$ und $-^{\infty}$)

Die $O$-Notation, die sogenannte Landau-Symbolik, ($O$ wie in Oh!, nicht $0$ wie in $1-1=0$) ist ein Werkzeug, um Folgen nach ihrem Wachstumsverhalten zu klassifizieren. Für eine Folge $f=(f_n)$ wird die Klasse $O(f)$ alle Folgen enthalten, die bis auf einen konstanten Faktor nicht schneller wachsen als $f$.

Wir schreiben eine Folge $(f_n)$ jetzt kurz und einfach z.B. als $n^2$ an Stelle von $n\mapsto n^2$.

In einer Klasse von Folgen $O(n^2)$ ("welche in der Ordnung von $n^2$ steigen") wollen wir Folgen zusammenfassen, mit einem bestimmten Divergenzverhalten, z.B.:

• $n$, weil $n\le n^2$,

• $16n^2$, weil uns ein konstanter Faktor 16 nicht stört (nach wie vor gilt, dass sich mit doppeltem $n$ das $f_n$​ vervierfacht: in diesem Sinn wachsen $n^2$ und $16n^2$ gleich schnell),

• $n^2+n+1$, weil das kleiner ist als $3n^2$, aber nicht $2^n$, weil man für jedes $C\in\mathbb{R}$ ein $n$ finden kann mit $2^n>C\cdot n^2$

Mathematisch sieht das so aus: $f_n \in O(g_n) :\Leftrightarrow \exists C>0, n_0\in\mathbb{N}:\forall n>n_0: |f_n| \leq C\cdot g_n$

Neu ist das $n_0$: Die Ungleichung muss nicht für alle Glieder gelten, sondern erst ab einem bestimmten Index (also für sehr große $n$); endlich viele Ausnahmen sind erlaubt. Endlich viele Ausnahmen könnte man auch versuchen durch größeres $n$ zuzulassen. Geht aber nicht für $g_n=0$.

Unter der Voraussetzung $\forall n:g_n>0$ kann man umschreiben zu

In dieser Form ist das $n_0$ überflüssig: Die Folge $|f_n|/g_n$ muss beschränkt sein.

Sollte man an einem möglichst kleinen $C$ interessiert sein (normalerweise ist man das nicht), kann man sich auf die Suche nach dem größten Häufungspunkt der (beschränkten) Folge $|f_n|/g_n$ begeben: wenn man den noch um ein beliebiges $\epsilon>0$ vergrößert, hat man ja eine Zahl $C$, für die nur endlich viele der Quotienten größer sind.

Eine Menge heißt abgeschlossen, wenn sie alle ihre Häufungspunkte enthält. Beispiel: nicht abgeschlossen: $\mathbb{Q}$,$\ \rbrack0{,}1\lbrack$; abgeschlossen: $\mathbb{R}$, $\lbrack 0{,}1\rbrack$

Eine Menge kann abgeschlossen werden, indem man all ihre Häufungspunkte hinzunimmt: $\mathbb{Q} \rightarrow \mathbb{R}$