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 BildungsgesetzeBearbeiten

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   wird definiert

 

Ein Beispiel ist die Vorschrift   für alle   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.

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

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

Lösung:

  1.   für alle  
  2.   für alle  
  3.   für alle  

Rekursive BildungsgesetzeBearbeiten

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   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   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  -te Folgenglied berechnen. Bei einem expliziten Bildungsgesetz können wir   direkt in die gegebene Formel einsetzen. Bei einer rekursiven Bildungsvorschrift muss man erst einmal alle unbekannten   Vorgänger ausrechnen.

Verständnisfrage: Warum wird durch die alleinige Angabe von   für alle   keine Folge   eindeutig definiert?

Es fehlt der Rekursionsanfang. Je nach Wahl des Rekursionsanfangs ergibt sich eine andere Folge. So erhalten wir mit   die Folge   und über die Wahl   ergibt sich die Folge  . Beide Folgen erfüllen die Bedingung   für alle  , sind aber unterschiedlich. Es ist also wichtig, den Rekursionsanfang immer mit anzugeben.

Weitere AnmerkungenBearbeiten

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  . 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 FolgenBearbeiten

Beispiel (Angabe eines Funktionsterms (Explizite Bildungsvorschrift))

Wir definieren die Folge   in   durch   für alle  . Statt   schreiben wir auch  .

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

Wir definieren die Folge   in   durch   und für alle   setzen wir  . Dies ist eine Rekursionsvorschrift für die Folge  .

Wenn wir das  -te Folgenglied ausrechnen wollen, können wir zuerst   aus   berechnen. Anschließend können wir   aus   berechnen, indem wir den Term   ausrechnen. Das machen wir solange, bis wir bei   angekommen sind. Also wird durch die obige Rekursionsvorschrift eindeutig eine Folge definiert.

Beispiel (Folge der Primzahlen)

Definiere die Folge   in   als die aufsteigende Folge der Primzahlen, d.h. es soll   für alle   gelten und   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   eindeutig eine Primzahl   zugeordnet, so dass   für alle   gilt und es für jede Primzahl   ein   mit   gibt.

Kompliziertere BeispieleBearbeiten

Beispiel (Folge von positiven Nullstellen von Polynomen)

Für alle   definieren wir die Funktion  . Für alle   gibt es genau eine positive Zahl  , so dass   ist. Wir erhalten eine Folge  .

Natürlich müssen wir zeigen, dass   wohldefiniert ist. Wir müssen also zeigen, dass es für alle   genau ein   gibt mit  . Dazu kann man den Zwischenwertsatz und eine Regel zur Monotonie und Ableitung verwenden.

Obwohl wir nicht einen Funktionsterm angeben können, mit dem man   berechnen kann, haben wir hier eine Folge definiert. Übrigens haben wir, ohne es zu merken, eine Folge von Funktionen   definiert.

To-Do:
  • Link auf Artikel zum Zwischenwertsatz erstellen
  • Aufgabe zum Zwischenwertsatz erstellen, mit der die Wohldefiniertheit der Folge   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   wird durch einen Algorithmus angegeben. Dabei wird ein Folgenglied immer aus dem vorherigen Folgenglied folgendermaßen berechnet:

Man setzt  . Jedes Folgenglied   ist eine Aneinanderreihung von Ziffern, die nicht durch ein Komma getrennt werden. Beispielsweise ist  .

Sei   für ein   gegeben. Wir schreiben nun auf, wie oft eine Ziffer in   vorkommt, bevor (von links nach rechts gelesen) eine andere Ziffer vorkommt. Im Fall   schreiben wir also:   mal eine  , dann   mal eine   und dann   mal eine  .

Das Folgenglied   besteht aus der Aneinanderreihung der Ziffern, die wir gerade von   notiert haben. Für   bedeutet das  .

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

Bildungsgesetze findenBearbeiten

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.

AnmerkungenBearbeiten

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 VorgehensweiseBearbeiten

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   sein, während man bei rekursiven Bildungsvorschriften eine Zuordnungsvorschrift der Form   sucht.

Explizites Bildungsgesetz findenBearbeiten

Hier suchst du eine Zuordnung der Art  , 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   die Zahl   machen, aus   die Zahl   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  ,   und so weiter sind.

Der mathematische Ausdruck für Quadratzahlen ist  . Dementsprechend lautet das einfachste explizite Bildungsgesetz  .

Rekursives Bildungsgesetz findenBearbeiten

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   und dem Rekursionsschritt   zusammen. Hier sucht man also eine Funktion  , wie   mit Hilfe von   und   berechnet werden kann.

Der Rekursionsanfang in unserer Aufgabe ist bereits bekannt. Wir wissen, dass   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   stets eine ungerade Zahl ist:

       
2 1 4 3
3 4 9 5
4 9 16 7
5 16 25 9

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

 

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

 

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