Eine rekursive Bildungsvorschrift gibt an, wie man ein beliebiges Glied
einer Zahlenfolge aus seinem Vorgänger 
oder auch aus mehreren Vorgängern 
gewinnen kann und wie das Anfangsglied 
(und ggf. auch noch darauf folgende Glieder) der Folge lautet (lauten).Ein Beispiel für eine meist rekursiv definierte Folge ist die sogenannte FIBONACCI-Folge
(interaktives Rechenbeispiel).
Für diese gilt:
Als Anfangsteil der Folge ergibt sich hieraus:
Die Folge ist benannt nach dem italienischen Mathematiker LEONARDO VON
PISA (etwa 1180 bis etwa 1250), der den Beinamen FIBONACCI trug. LEONARDO
soll auf die Zahlen dieser Folge gestoßen sein, als er die folgende
(hier in heutiger Sprechweise formulierte) Frage untersuchte:
- Wie viele Kaninchenpaare können in einem Jahr von einem einzigen Paar gezeugt werden, wenn jedes Paar in jedem Monat ein neues Paar zeugt, das vom zweiten Monat an selbst wieder neue Paare zeugt usw., falls keine Todesfälle vorkommen?
LEONARDO nahm dieses Problem in sein 1202 erschienenes Buch "Liber abaci" auf, dessen Hauptanliegen es war, die Überlegenheit des arabischen Zahlensystems gegenüber dem römischen Zahlensystem aufzuzeigen. Er beschreibt darin ausführlich, wie sich die Anzahl der Kaninchenpaare Monat für Monat berechnen lässt und bemerkt abschließend, dass man so bis zu einer unendlichen Zahl von Monaten weiterrechnen kann.
Inzwischen gibt es eine Vielzahl populärer Einkleidungen des gekennzeichneten mathematischen Sachverhalts. Ein Beispiel dafür sei noch genannt:
- Viele Besucher steigen an schönen Sommertagen die Treppen zum
Potsdamer Schloss Sanssouci hinauf. Dabei "erklimmen" die
meisten die lange Treppe Stufe für Stufe, aber es gibt auch nicht
wenige, die der Kleinschrittigkeit bald überdrüssig werden
und deshalb versuchen, auch einmal zwei Stufen auf einmal zu nehmen
(was wegen der "Tiefe" der Stufen gar nicht so einfach ist).
Setzen wir einmal voraus, dass Anton und seine Freunde zwar die erste Stufe auf jeden Fall betreten, dann aber weiter nur eine oder aber zwei Stufen auf einmal. Wie viele verschiedene Möglichkeiten gibt es, die n-te Stufe zu erreichen?
Für kleine n ist der Sachverhalt noch leicht zu übersehen.
Sei etwa 
.
Dann gilt das in der folgenden Tabelle Zusammengestellte.
|
Stufe n
|
Anzahl der Möglichkeiten, Stufe n zu erreichen |
|
1
|
1 |
|
2
|
1; nämlich genau zweimal 1 Stufe |
|
3
|
2; nämlich genau dreimal 1 Stufe oder einmal 1 Stufe und einmal 2 Stufen |
|
4
|
3; nämlich (1, 1, 1, 1), (1, 1, 2), (1, 2, 1) |
|
5
|
5; nämlich (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (1, 2, 2) |
Für 
würde sich diese "Möglichkeiten-Folge" mit den Zahlen
8, 13, 21, 34, 55, 89, 144 fortsetzen – und das sind genau die Glieder
der FIBONACCI-Folge.
Anmerkung: Es lässt sich zeigen, dass
der Quotient zweier aufeinander folgender Glieder der FIBONACCI-Folge
dem Grenzwert 
zustrebt, d.h., je weiter man in der Folge fortschreitet, desto genauer
gilt 
.
Eine weitere bekannte rekursiv definierte Folge ist die sogenannte (3n
+ 1)-Folge. Für sie gilt:
Wie man sieht, hängt das Aussehen der 
von der Wahl des Startwerts
ab. Man erhält beispielsweise
- für
:
- für
:
- für
:
Schon diese Beispiele lassen erkennen, dass die Folgenglieder immer
gleich 1 bleiben, falls die 1 jemals erreicht wird. Die Anzahl der Schritte
bis zu diesem Fall hängt offenbar vom Startwert
ab. Bis heute offen ist aber nun die Frage, ob die
für alle Werte von
endlich ist, ob die 1 also immer erreicht wird.
Mit der Klärung dieses Problems haben sich zahlreiche Wissenschaftler
beschäftigt. So machte sich beispielsweise der polnisch-amerikanische
Mathematiker und Physiker STANISLAW MARCIN ULAM (1906 bis 1984; in den
USA u.a. an der Entwicklung der Wasserstoffbombe beteiligt) um die Verbreitung
der mit der
verbundenen Fragen verdient, weshalb diese Folge auch ULAM-Folge
genannt wird.
COLLATZ-Problem – nach dem deutschen
Mathematiker LOTHAR COLLATZ (1910 bis 1990) – und Syracus-Algorithmus
sind weitere Namen für die Vermutung, dass diese Folge irgendwann bei 1 endet.
Seit den 70er Jahren des vorigen Jahrhunderts ist eine schnell wachsende
Zahl von Publikationen hierzu erschienen, ohne dass jedoch bislang
ein Beweis für die genannte Vermutung gelang.