Mathe für Nicht-Freaks: Explizite und rekursive Bildungsgesetze für Folgen

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

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

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:

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.

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:

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:

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:

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.

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:

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,\dots$. 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.

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:

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:

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

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=\dots$ 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:

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:

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:

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

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}