Eine (unendliche) Folge im herkömmlichen Sinn entsteht durch "Hintereinanderschreiben" von Zahlen, z.B.:
Dabei ist die Reihenfolge wichtig, jede Zahl hat also ihre feste Position. Die Folge ist eine andere als
Definition
Mathematisch können wir eine Folge deshalb als Abbildung auffassen: Jeder Position wird eine Zahl zugeordnet. Die Abbildung generiert demnach die Folge der geraden Zahlen:
Die Schreibweise ist für Folgen eher nicht gebräuchlich. Eher benutzt man die Indexschreibweise . Meist aber einfach oder noch kürzer . Die Klammern vermeiden Verwechslungen mit , was das -te Glied der Folge bezeichnet.
Alternative Darstellungsmöglichkeiten
Partialsummen
Oft ist es praktischer, nicht die Folgenglieder explizit aufzuschreiben, sondern die Differenz zwischen benachbarten Folgengliedern. Man spricht dann von einer Reihe mit Reihengliedern und den Partialsummen:
(Man beachte, dass sich aus der Definition für den Folgenanfang ergibt.)
Rekursiv
Speziell in der Informatik treten (bei Kostenanalysen) oft rekursiv definierte Folgen auf, bei denen jede Zahl nach einer festen Vorschrift aus dem Vorgänger (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ührt auf die Folge sofern man vorher festgelegt hat, dass sein soll.
Beispiel: Die Vorschrift , liefert dagegen die Folge , also
Beispiel: Eine typische Anwendung von Folgen in der Informatik: die Laufzeit eines Programms für verschiedene Eingaben; etwa die Folge der Anzahl der Vergleiche, die ein Sortierprogramm zum Sortieren von Zahlen höchstens durchführt (Insert-Sort).
Bei Laufzeitvergleichen ist insbesondere interessant, wie sich die Laufzeiten für immer größere 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ür jedes .
Folgen mit heißen streng monoton wachsend.
Eine Folge heißt entsprechend monoton fallend bzw. streng monoton fallend, wenn die Elemente kleiner werden, also bzw. .
Obere/ untere Schranken
Mindest- oder Maximallaufzeiten sind wichtig, daher sind wir an oberen/unteren Schranken für unsere Folgenelemente interessiert:
Gibt es eine Zahl mit für alle , dann nennt man eine obere Schranke.
Alle Zahlen, die größer als sind, sind natürlich erst recht obere Schranken; am interessantesten ist daher eine kleinste obere Schranke, die heißt dann Supremum: .
Entsprechend heißt ein mit für alle eine untere Schranke, besonders interessant ist hier eine größte untere Schranke, die heißt Infimum: .
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 im Grenzwert sehr großer passiert.
Der "gutmütige" Fall dabei ist, dass die Folge gegen eine Grenzwert konvergiert, d.h., dass für hinreichend großes alle Folgenglieder beliebig nahe an liegen:
Zur Erklärung: definiere die -Umgebung einer Zahl
"Beliebig nahe an " heißt nun, dass für jedes (noch so kleine) die Folgenglieder ab einem in liegen.
Es dürfen also insbesondere nur endlich viele Folgenglieder außerhalb von liegen! Für kleineres muss man dann meist ein größeres nehmen.
Konvergenz heißt also:
In diesem Fall heißt der Grenzwert der Folge: .
Beispiele:
(wähle ),
(umformen zu ),
Konvergenz durch monotone, beschränkte Folgen
Ein nützlicher Satz zur Konvergenz:
Häufungspunkte - limes superior und limes inferior
Die Folge mit konvergiert nicht gegen einen Grenzwert, aber die Werte und 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 die Folge mit Wegen der Beschränktheit von ist auch beschränkt, weiter ist monoton fallend (warum?), mithin konvergent und der Grenzwert
ist der größte Wert, für den in jeder Umgebung unendlich viele 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 einer beschränkten Folge gilt, dass für jedes nur endlich viele größer als sind.
Wären unendlich viele Glieder größer als , 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: ( und ) oder ( und )
Die -Notation, die sogenannte Landau-Symbolik, ( wie in Oh!, nicht wie in ) ist ein Werkzeug, um Folgen nach ihrem Wachstumsverhalten zu klassifizieren. Für eine Folge wird die Klasse alle Folgen enthalten, die bis auf einen konstanten Faktor nicht schneller wachsen als .
Wir schreiben eine Folge jetzt kurz und einfach z.B. als an Stelle von .
In einer Klasse von Folgen ("welche in der Ordnung von steigen") wollen wir Folgen zusammenfassen, mit einem bestimmten Divergenzverhalten, z.B.:
, weil ,
, weil uns ein konstanter Faktor 16 nicht stört (nach wie vor gilt, dass sich mit doppeltem das vervierfacht: in diesem Sinn wachsen und gleich schnell),
, weil das kleiner ist als , aber nicht , weil man für jedes ein finden kann mit
Mathematisch sieht das so aus:
Neu ist das : Die Ungleichung muss nicht für alle Glieder gelten, sondern erst ab einem bestimmten Index (also für sehr große ); endlich viele Ausnahmen sind erlaubt. Endlich viele Ausnahmen könnte man auch versuchen durch größeres zuzulassen. Geht aber nicht für .
Unter der Voraussetzung kann man umschreiben zu
In dieser Form ist das überflüssig: Die Folge muss beschränkt sein.
Sollte man an einem möglichst kleinen interessiert sein (normalerweise ist man das nicht), kann man sich auf die Suche nach dem größten Häufungspunkt der (beschränkten) Folge begeben: wenn man den noch um ein beliebiges vergrößert, hat man ja eine Zahl , 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: ,; abgeschlossen: ,
Eine Menge kann abgeschlossen werden, indem man all ihre Häufungspunkte hinzunimmt: