Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Vorwort

In diesem Buch möchte ich mich mit linearen Rekursionsgleichungen und den erzeugenden Funktionen ihrer Folgen befassen. Wenngleich die zu verwendenden Techniken nicht neu oder schwierig sind, so bleibt die Behandlung des Themas üblicherweise außerhalb der Lehrbücher. Das ist auch deswegen bedauerlich, weil sich ganzzahlige Folgen wie die Fibonaccizahlen u. ä. ausdauernder Beliebtheit erfreuen und das Rad der Berechnung ihrer geschlossenen Form trotzdem ständig neu erfunden wird. Darüber hinaus ist das Rechnen mit erzeugenden Funktionen ein unabdingbarer Bestandteil der Kombinatorik.

In den ersten Kapiteln werden wir sehen, dass die durch lineare Rekurrenzen definierten Zahlenfolgen, wenn sie als Koeffizienten in Potenzreihen eingesetzt werden, zu erzeugenden (generierenden) Funktionen führen, die rational sind. Umgekehrt erzeugt jede rationale Funktion eine Potenzreihe, deren Koeffizienten mindestens einer linearen Rekurrenz genügen.

In den darauf folgenden Kapiteln wird ersichtlich werden, dass diese Zuordnung mehrere Vorteile hat, insbesondere bei der Berechnung der sogenannten geschlossenen Form der erzeugten Zahlenfolge. Wir hoffen, dass die vermittelten Techniken auch anhand der großen Menge von Beispielen deutlich werden. Obwohl es möglich wäre, alle Methoden in Software zu realisieren, ist dies unseres Wissens (2007) noch nirgendwo implementiert, daher sollten die Beispiele auch als Testfälle für solche Software geeignet sein.

Das Buch ist eine Adaption ins Deutsche mit freundlicher Genehmigung des Autors des Werks von R. Stephan: Exercises With Linear Recurrences.[1] Es handelt sich aber nicht um eine reine Übersetzung, sondern eine völlige Neubearbeitung der enthaltenen Methoden und Beispiele.


-- Ayacop 10:10, 3. Feb. 2007 (CET)



  1. http://arxiv.org/abs/0704.2481