Explizite und rekursive Bildungsgesetze für Folgen – Serlo „Mathe für Nicht-Freaks“

Zur Definition einer Folge muss man eine Zuordnungsvorschrift angeben, die den einzelnen Indizes die Folgenglieder zuweist. Diese Zuordnungsvorschrift wird Bildungsgesetz der Folge (manchmal auch Bildungsvorschrift) genannt. Diese Zuordnungsvorschrift kann im Allgemeinen sehr kompliziert sein. Da eine Folge stets unendlich viele Glieder besitzt, kann man die Zuordnungsvorschrift nicht durch Aufzählung aller Folgenglieder definieren. Stattdessen gibt es andere Möglichkeiten wie explizite und rekursive Bildungsgesetze.

Explizite Bildungsgesetze

Bei einer expliziten Bildungsvorschrift wird ein vom Index der Folge abhängiger Funktionsterm angegeben, mit der man die einzelnen Folgenglieder ausrechnen kann. Ein solches Bildungsgesetz wird meist folgendermaßen aufgeschrieben: Für alle $n\in \mathbb {N}$ wird definiert

$a_{n}:={\text{ irgendein Term mit }}n$

Ein Beispiel ist die Vorschrift $a_{n}=n^{2}$ für alle $n\in \mathbb {N}$ für die Folge aller Quadratzahlen. Man kann diese Folge so aufschreiben:

${\begin{aligned}(a_{n})_{n\in \mathbb {N} }=\left(n^{2}\right)_{n\in \mathbb {N} }&=(1^{2},\,{\color {OliveGreen}2^{2}},\,{\color {RedOrange}3^{2}},\,{\color {Fuchsia}4^{2}},\ldots )\\&=(1,\,{\color {OliveGreen}4},\,{\color {RedOrange}9},\,{\color {Fuchsia}16},\ldots )\end{aligned}}$

Eine explizite Bildungsvorschrift der Folge zeichnet sich dadurch aus, dass die einzelnen Folgenglieder berechnet werden können, ohne andere Folgenglieder kennen zu müssen. Wenn man also ein bestimmtes Folgenglied berechnen möchte, so muss man nur den gewünschten Index in die Formel der expliziten Bildungsvorschrift einsetzen und den Wert dieser Formel berechnen.

Verständnisfrage: Wie lauten die expliziten Bildungsgesetze der folgenden Folgen?

1. Folge der Kubikzahlen
2. Folge der ungeraden Zahlen
3. Folge der Potenzen von $2$

Lösung:

1. $a_{n}=n^{3}$ für alle $n\in \mathbb {N}$
2. $b_{n}=2n-1$ für alle $n\in \mathbb {N}$
3. $c_{n}=2^{n}$ für alle $n\in \mathbb {N}$

Rekursive Bildungsgesetze

Eine rekursive Bildungsvorschrift zeichnet sich dadurch aus, dass man zur Berechnung einzelner Folgenglieder die Vorgänger dieser Folgenglieder kennen muss. Dies erkennt man daran, dass in der Funktion zur Berechnung eines Folgenglieds die vorhergehenden Folgenglieder mit auftauchen. Allgemein kann eine reelle Folge $(a_{n})_{n\in \mathbb {N} }$ folgendermaßen rekursiv definiert werden:

${\begin{aligned}a_{1}&:=r{\text{ für ein }}r\in \mathbb {R} \\[0.3em]a_{n+1}&:={\text{irgendein Term mit }}n,a_{1},a_{2},\ldots ,a_{n}\ {\text{ für alle }}n\in \mathbb {N} \end{aligned}}$

Da man zur Berechnung einzelner Folgenglieder bereits die Vorgänger kennen muss, muss bei der rekursiven Definition einer Folge das erste Folgenglied explizit benannt werden. So ist ein Beispiel für ein rekursives Bildungsgesetz:

${\begin{aligned}a_{1}&=-6\\a_{n+1}&=a_{n}+2\ {\text{ für alle }}n\in \mathbb {N} \end{aligned}}$

Die erste Formel $a_{1}=-6$ definiert das erste Folgenglied explizit und wird Rekursionsanfang genannt. Durch die zweite Formel, welche man Rekursionsschritt nennt, kann ein neues Folgenglied aus dessen Vorgänger berechnet werden. Zunächst gibt man über den Rekursionsanfang das erste Folgenglied vor und berechnet dann durch wiederholte Anwendung des Rekursionsschritts weitere Folgenglieder. Es ist:

${\begin{aligned}a_{1}&={\color {Blue}-6}\\a_{2}&=a_{1+1}=a_{1}+2={\color {Blue}-6}+2={\color {OliveGreen}-4}\\a_{3}&=a_{2+1}=a_{2}+2={\color {OliveGreen}-4}+2={\color {RedOrange}-2}\\a_{4}&=a_{3+1}=a_{3}+2={\color {RedOrange}-2}+2=0\\&\vdots \end{aligned}}$

Rekursive Bildungsgesetze für Folgen sind meist einfacher zu finden als explizite Bildungsvorschriften. Bei expliziten Bildungsvorschriften sind aber die Eigenschaften einer Folge meist einfacher aus dem Bildungsgesetz ablesbar als bei rekursiv definierten Folgen. Auch ist bei expliziten Bildungsvorschriften die Berechnung der Folgenglieder einfacher. Angenommen, wir möchten das $1000$-te Folgenglied berechnen. Bei einem expliziten Bildungsgesetz können wir $1000$ direkt in die gegebene Formel einsetzen. Bei einer rekursiven Bildungsvorschrift muss man erst einmal alle unbekannten $998$ Vorgänger ausrechnen.

Verständnisfrage: Warum wird durch die alleinige Angabe von $a_{n+1}=a_{n}+2$ für alle $n\in \mathbb {N}$ keine Folge $(a_{n})_{n\in \mathbb {N} }$ eindeutig definiert?

Es fehlt der Rekursionsanfang. Je nach Wahl des Rekursionsanfangs ergibt sich eine andere Folge. So erhalten wir mit $a_{1}=-6$ die Folge $(a_{n})_{n\in \mathbb {N} }=(-6,\,-4,\,-2,\,0,\,2,\,\ldots )$ und über die Wahl $a_{1}=10$ ergibt sich die Folge $(a_{n})_{n\in \mathbb {N} }=(10,\,12,\,14,\,16,\,18,\,\ldots )$. Beide Folgen erfüllen die Bedingung $a_{n+1}=a_{n}+2$ für alle $n\in \mathbb {N}$, sind aber unterschiedlich. Es ist also wichtig, den Rekursionsanfang immer mit anzugeben.

Weitere Anmerkungen

Wenn das Bildungsgesetz besonders einfach ist, schreibt man manchmal nur die ersten Folgenglieder einer Folge auf und überlässt dem Leser die Aufgabe, die Bildungsvorschrift zu finden. Ein Beispiel ist:

$(a_{n})_{n\in \mathbb {N} }=(1,\,2,\,3,\,4,\,5,\,\ldots )$

Diese Definition einer Folge hat aber den Nachteil, dass sie nicht eindeutig ist. Es ist nämlich nicht eindeutig festgelegt, wie eine solche Folge fortgesetzt werden muss. Man geht vielmehr davon aus, dass jeder Leser die Folge auf dieselbe Art und Weise fortsetzt. Somit ist die obige Art, eine Folge anzugeben, keine mathematisch exakte Definition!

Außerdem gibt es Bildungsgesetze, die zwar durch einen Algorithmus angegeben werden können, für die aber bisher weder explizite noch rekursive Bildungsgesetze bekannt sind. Ein Beispiel dafür ist die Folge der Primzahlen $2,\,3,\,5,\,7,\,11,\,\ldots$. Man kann zwar einen Algorithmus angeben, der alle Primzahlen nacheinander ausrechnet (zum Beispiel mit Hilfe des Siebs des Eratosthenes). Es ist aber bisher kein explizites oder rekursives Bildungsgesetz dieser Folge bekannt.

Beispiele zur Bildung von Folgen

Beispiel (Angabe eines Funktionsterms (Explizite Bildungsvorschrift))

Wir definieren die Folge $(a_{n})_{n\in \mathbb {N} }$ in $\mathbb {N}$ durch $a_{n}:=n^{3}+7$ für alle $n\in \mathbb {N}$. Statt $(a_{n})_{n\in \mathbb {N} }$ schreiben wir auch $(n^{3}+7)_{n\in \mathbb {N} }$.

Beispiel (Berechnung eines Folgenglieds in Abhängigkeit von vorherigen Folgengliedern (Rekursive Bildungsvorschrift))

Wir definieren die Folge $(a_{n})_{n\in \mathbb {N} }$ in $\mathbb {R}$ durch $a_{1}:=1$ und für alle $n\geq 2$ setzen wir $a_{n}:=(a_{n-1}+1)^{2}$. Dies ist eine Rekursionsvorschrift für die Folge $(a_{n})_{n\in \mathbb {N} }$.

Wenn wir das $n$-te Folgenglied ausrechnen wollen, können wir zuerst $a_{2}=(a_{1}+1)^{2}$ aus $a_{1}$ berechnen. Anschließend können wir $a_{3}$ aus $a_{2}$ berechnen, indem wir den Term $a_{3}=(a_{2}+1)^{2}$ ausrechnen. Das machen wir solange, bis wir bei $n$ angekommen sind. Also wird durch die obige Rekursionsvorschrift eindeutig eine Folge definiert.

Beispiel (Folge der Primzahlen)

Definiere die Folge $(p_{n})_{n\in \mathbb {N} }=(2,3,5,7,11,\ldots )$ in $\mathbb {N}$ als die aufsteigende Folge der Primzahlen, d.h. es soll $p_{n}<p_{n+1}$ für alle $n\in \mathbb {N}$ gelten und $\{p_{n}:n\in \mathbb {N} \}$ soll die Menge aller Primzahlen sein.

Diese Definition hört sich sehr abstrakt an und es ist nicht klar, wie man ein bestimmtes Folgenglied ausrechnet. Dennoch wird dadurch eindeutig eine Folge definiert. Das zeigt die folgende Überlegung:

Die Menge aller Primzahlen ist eine Teilmenge der natürlichen Zahlen. Also können wir die Primzahlen der Größe nach ordnen und anschließend durchnummerieren. Da es unendlich viele Primzahlen gibt, wird dadurch jeder natürlichen Zahl $n$ eindeutig eine Primzahl $p_{n}$ zugeordnet, so dass $p_{n}<p_{n+1}$ für alle $n\in \mathbb {N}$ gilt und es für jede Primzahl $p$ ein $n\in \mathbb {N}$ mit $p=p_{n}$ gibt.

Kompliziertere Beispiele

Beispiel (Folge von positiven Nullstellen von Polynomen)

Für alle $n\in \mathbb {N}$ definieren wir die Funktion $f_{n}:\mathbb {R} \to \mathbb {R} ,x\mapsto x^{n}+4n^{2}x-10$. Für alle $n\in \mathbb {N}$ gibt es genau eine positive Zahl $a_{n}$, so dass $f_{n}(a_{n})=0$ ist. Wir erhalten eine Folge $(a_{n})_{n\in \mathbb {N} }$.

Natürlich müssen wir zeigen, dass $(a_{n})_{n\in \mathbb {N} }$ wohldefiniert ist. Wir müssen also zeigen, dass es für alle $n\in \mathbb {N}$ genau ein $a_{n}\in \mathbb {R} ^{+}$ gibt mit $f_{n}(a_{n})=0$. Dazu kann man den Zwischenwertsatz und eine Regel zur Monotonie und Ableitung verwenden.

Obwohl wir nicht einen Funktionsterm angeben können, mit dem man $a_{n}$ berechnen kann, haben wir hier eine Folge definiert. Übrigens haben wir, ohne es zu merken, eine Folge von Funktionen $(f_{n})_{n\in \mathbb {N} }$ definiert.

To-Do:

• Link auf Artikel zum Zwischenwertsatz erstellen
• Aufgabe zum Zwischenwertsatz erstellen, mit der die Wohldefiniertheit der Folge $(a_{n})_{n\in \mathbb {N} }$ gezeigt wird

Beispiel (Folge der Primzahlen (Algorithmus))

Für die Folge der Primzahlen gibt es Bildungsgesetze, die durch einen Algorithmus angegeben werden können. Beispielsweise kann man mit Hilfe des Siebs des Eratosthenes alle Primzahlen nacheinander ausrechnen. Es ist aber bisher kein explizites oder rekursives Bildungsgesetz dieser Folge bekannt.

Beispiel (Conway-Folge (Algorithmus))

Die Conway-Folge $(c_{n})_{n\in \mathbb {N} }$ wird durch einen Algorithmus angegeben. Dabei wird ein Folgenglied immer aus dem vorherigen Folgenglied folgendermaßen berechnet:

Man setzt $c_{1}:=1$. Jedes Folgenglied $c_{n}$ ist eine Aneinanderreihung von Ziffern, die nicht durch ein Komma getrennt werden. Beispielsweise ist $c_{5}=111221$.

Sei $c_{n}$ für ein $n\in \mathbb {N}$ gegeben. Wir schreiben nun auf, wie oft eine Ziffer in $c_{n}$ vorkommt, bevor (von links nach rechts gelesen) eine andere Ziffer vorkommt. Im Fall $n=5$ schreiben wir also: $3$ mal eine $1$, dann $2$ mal eine $2$ und dann $1$ mal eine $1$.

Das Folgenglied $c_{n+1}$ besteht aus der Aneinanderreihung der Ziffern, die wir gerade von $c_{n}$ notiert haben. Für $n=5$ bedeutet das $c_{6}=312211$.

Siehe dazu auch den Wikipedia-Artikel zur Conway-Folge.

Bildungsgesetze finden

Manchmal steht man vor der Aufgabe, Bildungsgesetze für Folgen zu finden, für die die ersten Folgenglieder beispielhaft angegeben wurden. So könnte man sich für ein Bildungsgesetz der folgenden Folge interessieren:

$1,{\color {OliveGreen}4},{\color {RedOrange}9},{\color {Fuchsia}16},{\color {Blue}25},\ldots$

Wo spielt eine solche Aufgabenstellung eine Rolle? Zunächst ist es ein beliebter Aufgabentyp von LehrerInnen für SchülerInnen, wenn diese den Folgenbegriff im Unterricht einführen. Als Schüler kannst du dabei deine Fähigkeiten verbessern, Muster zu erkennen und diese durch mathematische Funktionen auszudrücken.

Aber auch Mathematikern begegnet eine solche Aufgabe. So ist es manchmal möglich, von einer gesuchten Folge die ersten Folgenglieder auszurechnen, ohne die Bildungsvorschrift kennen zu müssen. Aus diesen Folgengliedern versucht dann der Mathematiker, ein Bildungsgesetz zu erraten. Danach kann er versuchen zu beweisen, dass dieses Bildungsgesetz auch wirklich die gesuchte Folge beschreibt. Natürlich ist diese Strategie nicht immer erfolgreich, führt aber oft zum Ziel.

Anmerkungen

Folgenangaben wie die obige, die nur die ersten Folgenglieder aufzählen, sind nicht eindeutig. Es ist nämlich nirgends definiert, wie der Leser die Aufzählung der Folgenglieder fortsetzen muss. Insofern gibt es auch nicht das Bildungsgesetz, welches die Aufgabe löst. Man kann sogar zeigen, dass es stets unendlich viele Bildungsvorschriften gibt, deren Folge die genannten Zahlen als erste Folgenglieder besitzt. Deswegen sucht man auch nur ein mögliches Bildungsgesetz. Dieses sollte dabei möglichst einfach sein. Was aber ein einfaches Bildungsgesetz ist, ist wiederum eine subjektive Frage.

Auch gibt es keinen Standardweg, um eine solche Aufgabe zu lösen. Hier muss man (zum Teil lange) knobeln und viel rumprobieren. Insofern ist es auch völlig normal, wenn du am Anfang Probleme haben solltest, ein Bildungsgesetz zu finden. Je mehr Erfahrungen du mit Folgen sammelst, desto einfacher wirst du diese Aufgaben lösen können.

Allgemeine Vorgehensweise

Unabhängig davon, ob man ein rekursives oder ein explizites Bildungsgesetz finden möchte, bietet sich folgende Vorgehensweise an:

1. Erkenne ein Muster in der Folge. Hierzu sollte man sich zunächst fragen, was die nächsten Folgenglieder sein müssten. Wenn man diese gefunden hat, dann kann man sich fragen, warum es diese Folgenglieder sein müssen. Die Antwort auf diese Frage ist dann das gesuchte Muster der Folgenglieder.
2. Drücke das gefundene Muster mittels einer mathematischen Funktion aus. Bei expliziten Bildungsvorschriften muss es eine Funktion der Form $n\mapsto a_{n}$ sein, während man bei rekursiven Bildungsvorschriften eine Zuordnungsvorschrift der Form $(a_{n},n)\mapsto a_{n+1}$ sucht.

Explizites Bildungsgesetz finden

Hier suchst du eine Zuordnung der Art $n\mapsto a_{n}$, also einen Zusammenhang zwischen dem Index zu dem Folgenglied. Nehmen wir hierzu unsere Beispielaufgabe, eine explizite Bildungsvorschrift für folgende Folge zu finden:

$1,{\color {OliveGreen}4},{\color {RedOrange}9},{\color {Fuchsia}16},{\color {Blue}25},\ldots$

Gesucht ist also eine Funktion, die folgende Zuordnung erfüllt:

${\begin{aligned}1&\mapsto 1\\2&\mapsto {\color {OliveGreen}4}\\3&\mapsto {\color {RedOrange}9}\\4&\mapsto {\color {Fuchsia}16}\\5&\mapsto {\color {Blue}25}\\&\vdots \end{aligned}}$

Die gesuchte Funktion muss also aus $1$ die Zahl $1$ machen, aus $2$ die Zahl $4$ machen und so weiter. Du hast vielleicht schon erkannt, dass die Folgenglieder stets die Quadratzahlen ihrer Indizes sind. Es wäre also möglich, dass die nächsten Folgenglieder die Zahlen $36$, $49$ und so weiter sind.

Der mathematische Ausdruck für Quadratzahlen ist $n^{2}$. Dementsprechend lautet das einfachste explizite Bildungsgesetz $a_{n}=n^{2}$.

Rekursives Bildungsgesetz finden

Rekursive Bildungsvorschriften beschreiben den Zusammenhang eines Folgenglieds in Abhängigkeit von seinen Vorgängern. In der Regel (aber nicht immer) setzt sich ein rekursives Bildungsgesetz aus dem Rekursionsanfang $a_{1}=\ldots$ und dem Rekursionsschritt $a_{n+1}=f(a_{n},n)$ zusammen. Hier sucht man also eine Funktion $f$, wie $a_{n+1}$ mit Hilfe von $a_{n}$ und $n$ berechnet werden kann.

Der Rekursionsanfang in unserer Aufgabe ist bereits bekannt. Wir wissen, dass $a_{1}=1$ ist. Für den Rekursionsschritt suchen wir jetzt eine Funktion, die folgende Zuordnungen erfüllt:

${\begin{array}{lll}n=2,&a_{1}=1&\mapsto a_{2}={\color {OliveGreen}4}\\n=3,&a_{2}={\color {OliveGreen}4}&\mapsto a_{3}={\color {RedOrange}9}\\n=4,&a_{3}={\color {RedOrange}9}&\mapsto a_{4}={\color {Fuchsia}16}\\n=5,&a_{4}={\color {Fuchsia}16}&\mapsto a_{5}={\color {Blue}25}\\&&\vdots \end{array}}$

Diese Zuordnung ist nicht so offensichtlich. Man sieht aber vielleicht, dass die Differenz $a_{n}-a_{n-1}$ stets eine ungerade Zahl ist:

$n$	$a_{n-1}$	$a_{n}$	$a_{n}-a_{n-1}$
2	1	4	3
3	4	9	5
4	9	16	7
5	16	25	9

Für $n=2$ haben wir die ungerade Zahl $3$, für $n=3$ die ungerade Zahl $5$ und so weiter. Diese ungeraden Zahlen können nun durch $n$ ausgedrückt werden. Die Differenz ist nämlich gleich $2n-1$. So erhalten wir $a_{n}-a_{n-1}=2n-1$, welches man umstellen kann zu:

$a_{n}=a_{n-1}+2n-1$

Nun wollen wir aber einen Rekursionsschritt der Form $a_{n+1}=...$ haben. Setzen wir in der obigen Gleichung also anstelle von $n$ die Zahl $m+1$ ein. Jede natürliche Zahl $n$ größer gleich 2 ist ja darstellbar als Summe $m+1$, wobei $m$ der Vorgänger von $n$ ist. Wir erhalten:

${\begin{aligned}&&a_{n}&=a_{n-1}+2n-1\\&\implies &a_{m+1}&=a_{(m+1)-1}+2(m+1)-1\\&\implies &a_{m+1}&=a_{m}+2m+1\end{aligned}}$

Nun können wir wieder $n$ anstelle von $m$ einsetzen. Insgesamt ergibt sich damit die rekursive Bildungsvorschrift:

${\begin{aligned}a_{1}&=1\\a_{n+1}&=a_{n}+2n+1\end{aligned}}$