Rekursive Definitionen spezieller Zahlenfolgen

FIBONACCI-Folge

Für die meist rekursiv definierte sogenannte FIBONACCI-Folge gilt:
$a_1=1;a_2=1;a_{n+2}=a_{n+1}+a_n$

Als Anfangsteil der Folge ergibt sich hieraus:
$1;1;2;3;5;8;13;21;\mathrm{...}$

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 $n=5$. Dann gilt das in der folgenden Tabelle Zusammengestellte.

Für $n=6$ bis $n=12$ 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 $\frac{1+\sqrt{5}}{2}\approx \mathrm{1,618}$ zustrebt, d.h., je weiter man in der Folge fortschreitet, desto genauer gilt $a_{n+1}\approx \mathrm{1,618}\cdot a_n$.

$\left(3n+1\right)\text{-Folge}$ (ULAM-Folge)

Eine weitere bekannte rekursiv definierte Folge ist die sogenannte (3n + 1)-Folge.
Für sie gilt:
$a_{n+1}=\{\begin{array}{ll}1,\hfill & falls{a}_n=1\hfill \\ 3a_{n+1},\hfill & falls{a}_{n}ungerade\hfill \\ \frac{a_n}{2},\hfill & falls{a}_{n}gerade\hfill \end{array}{a}_1=a(beliebig)$

Wie man sieht, hängt das Aussehen der $\left(3n+1\right)\text{-Folge}$ von der Wahl des Startwerts $a_1$ ab. Man erhält beispielsweise

• für $a_1=3$:
  $10;5;16;8;4;2;1;1;\mathrm{....}$
• für $a_1= 7$:
  $\begin{array}{l}\text{7;}\text{22;}\text{11;}\text{34;}\text{17;}\text{52;}\text{26;}\text{13;}\text{40;}\text{20;}\\ \text{10;}\text{5;}\text{16;}\text{8;}\text{4;}\text{2;}\text{1;}\text{1;}\mathrm{....}\end{array}$
• für ${\text{a}}_{\text{1}}=100$:
  $\begin{array}{l}\text{100;}\text{50;}\text{25;}\text{76;}\text{38;}\text{19;}\text{58;}\text{29;}\text{88;}\text{44;}\\ \text{22;}\text{11;}\text{34;}\text{17;}\text{52;}\text{26;}\text{13;}\text{40;}\text{20;}\\ \text{10;}\text{5;}\text{16;}\text{8;}\text{4;}\text{2;}\text{1;}\text{1;}\mathrm{...}\end{array}$

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 $a_1$ ab. Bis heute offen ist aber nun die Frage, ob die $\left(3n+1\right)\text{-Folge}$ für alle Werte von $a_1$ 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 $\left(3n+1\right)\text{-Folge}$ 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.