Angabe von Anfangsgliedern

Die in manchen „Intelligenztests“ gestellte Aufgabe, eine Folge fortzusetzen, deren erste Glieder gegeben sind, ist aus mathematischer Sicht unsinnig. Auch durch noch so viele Anfangsglieder ist der weitere Verlauf einer Folge nicht eindeutig festgelegt. Es gibt nur mehr oder weniger plausible Fortsetzungen, die aber im Auge des Betrachters liegen und weder „richtig“ noch „falsch“ sind, sondern willkürlich sind. Um zu zeigen, dass eine Folge von Zahlen auf eine bestimmt Weise sich fortsetzt, muss man die Bildungsvorschrift der bekannten Glieder kennen und nicht nur mutmaßen. Das steht diesen „Intelligenztests“ aber entgegen.

Beispiele

• Gegeben ist 0, 1, 2, 3, …. Am plausibelsten ist die Fortsetzung 4, 5, 6, …, also die Folge aller natürlichen Zahlen. Möglich ist aber auch die Fortsetzung 0, 1, 2, 3, 0, …, und zwar als die periodische Folge der kleinsten positiven Reste der natürlichen Zahlen modulo 4. In einem Computer werden ganze Zahlen oft mit 32 Bit im Zweierkomplement, also als die absolut kleinsten Reste modulo 2³² dargestellt. Beim sukzessiven Erhöhen eines Registers (ohne Überlauftest) durchläuft man dann die Zahlenfolge 0, 1, 2, 3, …, 2147483647, −2147483648, −2147483647, …, −1 und periodisch weiter.
• Zu gegebenen n Folgengliedern kann man ein beliebiges Folgenglied hinzufügen und ein Polynom n. Grades dadurch legen. Damit kann man eine gegebene Folge beliebig fortsetzen und eine plausible mathematisch Bildungsvorschrift angeben.
• Für die Zahlenfolge 3, 1, 4, 1, 5, … ist eine plausible Fortsetzung 1, 6, 1, 7, … Andere würden die Dezimaldarstellung der Kreiszahl ${\displaystyle \pi }$ wiedererkennen und die Fortsetzung 9, 2, 6, … vorschlagen.
• Eine sehr interessante Zahlenfolge sind die Werte der Borwein-Integrale. Diese sind lange Zeit exakt ${\displaystyle \pi /2}$, um nach vielen Gliedern auf einmal den Wert zu ändern.
• Eine weitere legendäre Zahlenfolge ist 1, 2, 4, 8, 16, …, für die es mittlerweile mehr als 10 Beispiele für Folgen gibt, die nicht mit 32, 64, … weitergehen und die die Lösungen normaler Aufgaben sind. Am bekanntesten ist das Mosersche Kreisflächenproblem, auch als Pizza-Problem bekannt (Folge A000127 in OEIS).

Die Online-Enzyklopädie der Zahlenfolgen (OEIS) enthält zehntausende mathematisch relevanter Folgen. Darin kann man nach einer gegebenen Teilfolge suchen.

Angabe einer Funktionsvorschrift

Für viele, aber keineswegs alle Folgen kann man die Funktionsvorschrift

${\displaystyle i\mapsto a_{i}}$

als eine geschlossene Gleichung angeben.

In den folgenden Beispielen legen wir Indizes aus der Menge ${\displaystyle \mathbb {N} _{0}}$ zugrunde:

• Die Folge der natürlichen Zahlen 0, 1, 2, 3, … Dieses Beispiel ist speziell, weil die Werte von Folgenglied und Index übereinstimmen. Die Funktionsvorschrift lautet einfach

${\displaystyle a_{i}=i.}$

• Die Folge der ungeraden Zahlen 1, 3, 5, 7, … hat die Funktionsvorschrift

${\displaystyle a_{i}=2i+1.}$

• Die Folge der Zweierpotenzen 1, 2, 4, 8, …

${\displaystyle a_{i}=2^{i}.}$

Daran anknüpfende Aufgaben

Das Problem, zu einer gegebenen Funktionsvorschrift die Anfangsglieder zu bestimmen, ist einfach lösbar. Man nimmt nacheinander die Werte ${\displaystyle i=0}$, ${\displaystyle i=1}$, ${\displaystyle i=2}$ usw., setzt sie jeweils in die Funktionsvorschrift ein und berechnet auf diese Weise die Folgenglieder ${\displaystyle a_{0}}$, ${\displaystyle a_{1}}$, ${\displaystyle a_{2}}$ usw. Zweck dieser Rechnung ist es, sich ein erstes Bild vom Verlauf einer Folge zu machen. Aber Achtung: Eine Folge kann für wirklich große Indizes einen ganz anderen Verlauf nehmen als nach den ersten zehn oder hundert Gliedern zu erwarten war. Beispiel: die Folge ${\displaystyle a_{i}=1/(1+(i-1000)^{2})}$, die bis ${\displaystyle i=1000}$ monoton zunimmt, dann aber wieder abnimmt, wie man durch Einsetzen höherer Zehnerpotenzen überprüfen kann.

Die Umkehraufgabe, zu gegebenen Anfangsgliedern eine Funktionsvorschrift zu bestimmen, ist dagegen deutlich schwieriger. Streng genommen kann es gar keine eindeutige Lösung geben, denn jeder Folgenanfang lässt sich wie oben beschrieben in verschiedener Weise fortsetzen. In der Praxis wird diese Aufgabe daher nur für Folgen gestellt, deren Glieder ${\displaystyle a_{0}}$, ${\displaystyle a_{1}}$, ${\displaystyle a_{2}}$ usw. in einigermaßen überschaubarer Weise vom Index ${\displaystyle i=0,1,2,\dotsc }$ abhängen. Im Einzelnen können folgende Eigenschaften überprüft werden:

• Ist die Folge alternierend? Wenn ja, bekommt man das richtige Vorzeichen durch einen Faktor ${\displaystyle (-1)^{i}}$ in der Funktionsvorschrift. Beispiel: 0, −1, 2, −3, 4, … hat die Vorschrift ${\displaystyle a_{i}=(-1)^{i}\cdot i}$.
• Sind die Folgenglieder Brüche? Wenn ja, konstruiere man unabhängig voneinander Funktionsvorschriften für Zähler und Nenner. Beispiel: 1/1, 2/2, 3/4, 4/8, … hat die Vorschrift ${\displaystyle a_{i}=(i+1)/2^{i}}$.
• Nehmen die Folgenglieder um konstante Differenzen ${\displaystyle d}$ zu (oder ab, mit ${\displaystyle d<0}$)? Wenn ja, hat man eine arithmetische Folge ${\displaystyle a_{i}=a_{0}+d\cdot i}$. Beispiel: 1, 3, 5, 7, … hat die Vorschrift ${\displaystyle a_{i}=1+2i}$ .
• Genügen die Differenzen zwischen aufeinander folgenden Gliedern einem einfacheren Bildungsgesetz als die Folgenglieder selbst? Wenn ja, kann man die Folge als eine Reihe auffassen (siehe dazu unten). Beispiel: Für 1, 3, 6, 10, 15, … lauten die Differenzen 1, 2, 3, 4, …
• Stehen aufeinander folgende Folgenglieder in einem konstanten Verhältnis ${\displaystyle 1:q}$ zueinander? Wenn ja, hat man eine geometrische Folge ${\displaystyle a_{i}=a_{0}\cdot q^{i}}$ . Beispiel: Die Folge 100; 80; 64; 51,2; … nimmt von Glied zu Glied um einen Faktor 0,8 ab; also lautet die Vorschrift ${\displaystyle a_{i}=100\cdot {0{,}8}^{i}}$ .

Erschwert wird die Suche nach einer Funktionsvorschrift dadurch, dass die ersten ein oder zwei Folgenglieder (zu den Indizes 0 und 1) oft aus dem Rahmen zu fallen scheinen. Das liegt daran, dass ein Summand 0, ein Faktor 1 oder Exponent 0 oder 1 in aller Regel nicht ausgeschrieben, sondern sofort ausgerechnet werden. In der gekürzten Form 1, 1, 3/4, 1/2, … ist dem oben genannten Beispiel 1/1, 2/2, 3/4, 4/8, … die Funktionsvorschrift schwer anzusehen.

Angabe als Reihe

Eine Folge ${\displaystyle \left(s_{n}\right)_{n\in \mathbb {N} }}$, deren ${\displaystyle n}$-tes Glied die Summe der ersten ${\displaystyle n}$ Glieder einer anderen Folge ${\displaystyle \left(a_{i}\right)_{i\in \mathbb {N} }}$ ist, heißt eine Reihe:

${\displaystyle s_{n}=a_{0}+a_{1}+\dotsb +a_{n}=\sum _{i=0}^{n}a_{i}}$

Der mit Hilfe des Summenzeichens geschriebene Ausdruck ${\displaystyle \sum \nolimits _{i=0}^{n}a_{i}}$ ist also eine Abkürzung für den Ausdruck ${\displaystyle a_{0}+a_{1}+\dotsb +a_{n}}$. Innerhalb und außerhalb des Summenzeichens sind unterschiedliche Indizes zu verwenden. Dass speziell ${\displaystyle n}$ und ${\displaystyle i}$ gewählt wurden, entspricht einer weit verbreiteten Konvention, ist aber nicht zwingend.

Um ${\displaystyle s_{n}=\sum \nolimits _{i=0}^{n}a_{i}}$ als konkreten Zahlenwert zu berechnen, muss ein konkreter Zahlenwert für den Index ${\displaystyle n}$ vorgegeben werden. Im Gegensatz dazu ist der Index ${\displaystyle i}$ kein (von außen) vorzugebender Wert, sondern durch die Summationsvorschrift selbst festgelegt. Welches ${\displaystyle n}$ auch immer gegeben ist, für den Laufindex ${\displaystyle i}$ müssen nacheinander die Werte 0, 1, …, ${\displaystyle n}$ eingesetzt und die Summe der zugehörigen ${\displaystyle a_{0}}$, ${\displaystyle a_{1}}$, …, ${\displaystyle a_{n}}$ berechnet werden.

Man kann jede Folge ${\displaystyle \left(s_{n}\right)_{n\in \mathbb {N} }}$ als eine Reihe auffassen, indem man aus den Differenzen aufeinander folgender Glieder eine zugehörige Folge

${\displaystyle a_{i}={\begin{cases}s_{0}&{\text{wenn }}i=0,\\s_{i}-s_{i-1}&{\text{sonst}}\end{cases}}}$

konstruiert. Folge und Reihe sind also nicht scharf voneinander trennbar. Die Zeitreihen der Wirtschaftswissenschaftler sind eigentlich Folgen. Viele Erklärungsmodelle modellieren aber nicht absolute Werte, sondern deren zeitliche Veränderungen, was für die Auffassung der absoluten Werte als Glieder einer Reihe spricht.

Konkreten Nutzen bringt die Deutung einer Folge als Reihe, wenn man die Summation für beliebige ${\displaystyle n}$ ausführen kann. Summationsformeln sind zum Beispiel bekannt für die arithmetische Reihe und die geometrische Reihe.

Die Deutung einer unendlichen Folge als Reihe erleichtert es zu bestimmen, ob und wenn ja gegen welchen Grenzwert die Folge konvergiert. Für unendliche Reihen gibt es eigene Konvergenzkriterien. Umgekehrt kann man aus der Konvergenz einer Reihe (d. h., in obiger Schreibweise, der Konvergenz von ${\displaystyle \left(s_{n}\right)_{n\in \mathbb {N} }}$) immer darauf schließen, dass die Folge der Summanden (in obiger Schreibweise also die Folge ${\displaystyle \left(a_{n}\right)_{n\in \mathbb {N} }}$) gegen Null konvergiert.

Angabe einer Rekursion

Das Bildungsgesetz einer Folge kann auch rekursiv angegeben werden. Dazu nennt man ${\displaystyle m}$ Anfangswerte (mit ${\displaystyle m\geq 1}$; meistens ist ${\displaystyle m=1}$ oder ${\displaystyle m=2}$) sowie eine Vorschrift, wie ein Folgenglied ${\displaystyle a_{i}}$ aus den vorhergehenden ${\displaystyle m}$ Gliedern ${\displaystyle a_{i-m},\dotsc ,a_{i-1}}$ berechnet werden kann.

Das bekannteste Beispiel für eine Folge, die sich wesentlich einfacher durch eine Rekursionsvorschrift als durch eine Funktionsvorschrift beschreiben lässt, ist die Fibonacci-Folge 0, 1, 1, 2, 3, 5, 8, … Für sie ist ${\displaystyle m=2}$, gegeben sind die zwei Anfangsglieder ${\displaystyle a_{0}=0}$ und ${\displaystyle a_{1}=1}$ sowie die Rekursionsvorschrift

${\displaystyle a_{i}=a_{i-2}+a_{i-1}.}$

Die explizite Formel von Moivre und Binet für die Folgenglieder

${\displaystyle a_{i}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{i}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{i}\right)={\frac {\Phi ^{i}-{\bar {\Phi }}^{i}}{\Phi -{\bar {\Phi }}}}}$

steht in engem Zusammenhang mit dem Goldenen Schnitt und der Goldenen Zahl ${\displaystyle \Phi }$. Man beachte, dass die ${\displaystyle a_{i}}$ alle ganzzahlig sind, da sich die ungeraden Potenzen der ${\displaystyle {\sqrt {5}}}$ heraussubtrahieren.

Für manche Folgen kann man umgekehrt aus der Funktionsvorschrift eine Rekursionsvorschrift ableiten. Zum Beispiel folgt für die geometrische Folge aus der Funktionsvorschrift

${\displaystyle a_{i}=a_{0}\cdot q^{i}}$

die Rekursionsvorschrift

${\displaystyle a_{i}=q\cdot a_{i-1}.}$

Die Rekursion

${\displaystyle a_{1}=2,\quad a_{i+1}={\frac {a_{i}}{2}}+{\frac {1}{a_{i}}}}$

definiert die Folge rationaler Zahlen 2, 3/2, 17/12, …, die gegen ${\displaystyle {\sqrt {2}}}$ konvergiert.

Angabe über einen Algorithmus

Für manche Folgen gibt es eine klar definierte Konstruktionsvorschrift (Algorithmus), aber keine Funktionsvorschrift. Das bekannteste Beispiel ist die Folge der Primzahlen 2, 3, 5, 7, 11, … Bereits den alten Griechen (möglicherweise auch Indern) war es bekannt, wie man immer weitere Glieder dieser Folge berechnet. Eine Möglichkeit ist, das Sieb des Eratosthenes anzuwenden. Es gibt jedoch keine Methode, zu einem gegebenen ${\displaystyle i}$ die ${\displaystyle i}$-te Primzahl anzugeben, ohne zuvor die gesamte Folge von der ersten bis zur ${\displaystyle (i-1)}$-ten Primzahl zu bestimmen. Wenn man nicht die zehnte oder die hundertste, sondern die ${\displaystyle 10^{20}}$-te Primzahl wissen möchte, erhöht dies den Rechenaufwand stark.

Die Länge des kürzesten Algorithmus, der eine Folge erzeugt, heißt ihre Kolmogorow-Komplexität (manchmal wird diese Bezeichnung in einem engen Sinn nur für Zeichenfolgen, d. h. endliche Folgen mit endlichen Zielmengen ${\displaystyle X}$ verwendet). Sie hängt zwar von der verwendeten Programmiersprache ab; nach dem Invarianztheorem differieren die Längen für unterschiedliche Sprachen jedoch nur um eine nur sprachabhängige additive Konstante.

Monotonie

Beschränktheit

Sonstige

• Eine Folge, deren Werte abwechselnd positiv und negativ sind, heißt alternierend.
• Eine Folge, deren Glieder alle übereinstimmen, wird konstante Folge genannt.
• Eine Folge, deren Glieder alle ab einem bestimmten Glied übereinstimmen, wird stationäre Folge genannt
• Eine Folge, die gegen 0 konvergiert, heißt Nullfolge.
• Eine Folge, wird abbrechend genannt, falls sie ab einem bestimmten Glied 0 ist, d. h. eine stationäre Nullfolge.
• Eine Folge, die aus Wiederholungen einer endlichen Teilfolge besteht, heißt periodisch. Es gibt eine Periodenlänge ${\displaystyle n}$, und für alle ${\displaystyle i}$ aus ${\displaystyle \mathbb {N} }$ gilt: ${\displaystyle a_{i}=a_{i+n}}$. Teilfolge ist hier als Folge von ${\displaystyle [0,n]}$ in die gewählte Menge zu verstehen.

Eine interessante Aufgabe aus der Analysis besteht darin, zu ermitteln, ob eine Folge konvergiert, und im Falle der Konvergenz, gegen welchen Grenzwert. Eine unendliche Folge, die nicht konvergiert, kann nichtsdestoweniger Häufungspunkte besitzen (Beispiel: die Folge −1/2, 3/4, −5/6, 7/8, … besitzt die Häufungspunkte −1 und 1). Insbesondere hat jede beschränkte Folge in der Menge der reellen Zahlen mindestens einen Häufungspunkt (Satz von Bolzano-Weierstraß).

Die vorgenannte Charakterisierung einer Folge über ihr Steigungsverhalten und ihren Bildbereich kann helfen, zu bestimmen, ob und falls gegen welchen Grenzwert sie konvergiert. Besonders nützlich ist hierbei das Monotoniekriterium, nach dem eine monoton steigende, nach oben beschränkte Folge in der Menge der reellen Zahlen stets konvergiert, wobei ihr Grenzwert mit ihrem Supremum übereinstimmt (Beispiel: die Folge 0, 1/2, 2/3, 3/4, … konvergiert gegen ihr Supremum 1). Entsprechend konvergiert eine monoton fallende, nach unten beschränkte Folge gegen ihr Infimum.

Die Charakterisierungskriterien Monotonie und Beschränktheit lassen sich verallgemeinern für alle Folgen, deren Zielmenge ${\displaystyle X}$ geordnet ist. Konstante, stationäre und periodische Folgen lassen sich für beliebige Zielbereiche, konvergente Folgen für einen beliebigen metrischen Raum als Zielbereich definieren.

Arithmetische Folgen und Reihen

Eine arithmetische Folge ist eine Folge mit konstanter Differenz zwischen aufeinanderfolgenden Gliedern. Beispiele sind die häufig verwendeten Folgen der geraden Zahlen 2, 4, 6, … mit der Funktionsvorschrift

${\displaystyle a_{i}=2i}$

und die der ungeraden Zahlen mit der Funktionsvorschrift

${\displaystyle a_{i}=1+2i.}$

Allgemein lautet die Funktionsvorschrift

${\displaystyle a_{i}=a_{0}+i\cdot d,}$

wobei ${\displaystyle d}$ die konstante Differenz bezeichnet.

Folgen, die sich auf arithmetische Folgen zurückführen lassen, nennt man arithmetische Folgen höherer Ordnung. So ist die Folge der Dreieckszahlen eine arithmetische Folge 2. Ordnung.

Folge:	${\displaystyle 1\ }$		${\displaystyle 3\ }$		${\displaystyle 6\ }$		${\displaystyle 10\ }$		${\displaystyle 15\ }$		${\displaystyle \dotso \ }$
1. Differenzfolge:		${\displaystyle 2\ }$		${\displaystyle 3\ }$		${\displaystyle 4\ }$		${\displaystyle 5\ }$		${\displaystyle \dotso \ }$
2. Differenzfolge:			${\displaystyle 1\ }$		${\displaystyle 1\ }$		${\displaystyle 1\ }$		${\displaystyle \dotso \ }$

Arithmetische Folgen ${\displaystyle g}$-ter Ordnung sind genau diejenigen Folgen, die sich durch ein Polynom ${\displaystyle g}$-ten Grades beschreiben lassen. Dieses Polynom lässt sich durch Lagrange-Interpolation aus ${\displaystyle g}$ beliebigen Folgenglieder finden. Die Dreieckzahlen gehorchen z. B. dem Bildungsgesetz ${\displaystyle a_{i}={\frac {i^{2}}{2}}+{\frac {i}{2}}}$.

Folgen auf Basis der Potenzfunktion

Eine Potenzfolge ist eine Folge, für die die Potenzfunktion die Glieder liefert (Erzeugende Funktion)

Die Folge der Quadratzahlen: 0, 1, 4, 9, … hat die Funktionsvorschrift ${\displaystyle a_{i}=i^{2}}$. Die Folge der Quadratzahlen ist ebenfalls eine arithmetische Folge 2. Ordnung, da sie sich als Reihe auffassen lässt, der die Folge der ungeraden Zahlen zugrunde liegt.

Die Folge der Kubikzahlen 0, 1, 8, 27, … besitzt die Vorschrift

${\displaystyle a_{i}=i^{3},}$

was man für ${\displaystyle s}$-te Potenzen der natürlichen Zahlen zu

${\displaystyle a_{i}=i^{s}}$

verallgemeinern kann, wobei ${\displaystyle s}$ eine beliebige reelle Zahl sein darf. Mit ${\displaystyle s=1/2}$ erhält man die Folge ${\displaystyle 0,1,{\sqrt {2}},{\sqrt {3}},2,{\sqrt {5}},\dotsc }$ der Quadratwurzeln der natürlichen Zahlen,

${\displaystyle a_{i}=i^{0{,}5}={\sqrt {i}}}$.

Bei negativen Exponenten ${\displaystyle s<0}$ ist zu beachten, dass ${\displaystyle 0^{s}}$ nicht existiert. Beispielsweise ist es nicht möglich, mit ${\displaystyle s=-1}$ und der Funktionsvorschrift

${\displaystyle a_{i}=i^{-1}={\frac {1}{i}}}$ das Folgenglied zum Index ${\displaystyle i=0}$

zu berechnen. Man kann den Index 0 ausschließen, sich also auf die Indexmenge ${\displaystyle \mathbb {N} ^{+}}$ beschränken. Oft ist es jedoch zweckmäßiger, die Indexmenge ${\displaystyle \mathbb {N} _{0}}$ unverändert zu lassen und stattdessen die Funktionsvorschrift in

${\displaystyle a_{i}=(i+1)^{-1}={\frac {1}{i+1}}}$

abzuändern. Dann lauten die ersten Folgenglieder 1, 1/2, 1/3, 1/4, … In gleicher Weise kann man eine Funktionsvorschrift für beliebige Exponenten ${\displaystyle s}$ aufstellen:

${\displaystyle a_{i}=(i+1)^{s}.}$

Geometrische Folgen

So wie in einer arithmetischen Folge aufeinanderfolgende Glieder eine konstante Differenz haben, so stehen in einer geometrischen Folge

${\displaystyle a_{i}=a_{0}\cdot q^{i}}$

aufeinanderfolgende Glieder in einem konstanten Verhältnis zueinander, ${\displaystyle a_{i+1}/a_{i}=q}$. Zum Beispiel ergibt sich mit ${\displaystyle q=2}$ und ${\displaystyle a_{0}=1}$ die Folge der Zweierpotenzen

${\displaystyle a_{i}=2^{i},}$

also zum Beispiel für die ersten zehn Glieder die Folge 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 (jedes Glied ist doppelt so groß wie das vorangegangene). Wichtig ist diese Folge speziell für die Umwandlung von den in der Informatik verwendeten Dualzahlen in Dezimalzahlen (und umgekehrt). Eine geometrische Folge mit ${\displaystyle \vert q\vert <1}$ konvergiert gegen Null, wie beispielsweise die Folge 1; 0,1; 0,01; … zu ${\displaystyle q=0{,}1}$:

${\displaystyle a_{i}=\left({\frac {1}{10}}\right)^{i}.}$

Wenn ${\displaystyle q=1}$ erhält man die triviale Folge 1, 1, 1, …; wenn ${\displaystyle q=-1}$, erhält man aus

${\displaystyle a_{i}=(-1)^{i}}$

die fundamentale alternierende Folge 1, −1, 1, −1, …

Ein Beispiel für die Alltagsanwendung der geometrischen Folge ist die gleichstufige Stimmung der musikalischen Tonleiter – die aufeinanderfolgenden Glieder, hier Halbtonschritte, besitzen zueinander ein konstantes Frequenzverhältnis.