Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Homogene und inhomogene Rekurrenzen

Bevor wir zu den zentralen theoretischen Erkenntnissen kommen, die diesem Buch zugrunde liegen, ist es noch notwendig, zwei Arten von linearen Rekurrenzen zu betrachten. Wir werden sehen, dass nur sogenannte homogene Rekurrenzen auf einfache Weise handhabbar sind, und dass inhomogene Rekurrenzen in diese überführt werden können. Alle anderen Arten von Rekurrenzen können mit den dargestellten Methoden nicht gelöst werden. Zunächst jedoch:

Definition. Eine lineare Rekurrenz (auch Rekursion oder Differenzengleichung) besteht aus einer Gleichung der Form

$c_{k}a_{n+k}=c_{k-1}a_{n+k-1}+c_{k-2}a_{n+k-2}+\cdots +c_{0}a_{n}+f(n)$,

und vorgegebenen Anfangswerten

$a_{0},a_{1},\ldots ,a_{k-1}$

wobei n eine ganzzahlige Unbekannte und k eine positive ganze Zahl die Ordnung der Rekurrenz bezeichnet, und die c_i vorgegebene ganze Zahlen sind. Auch ist die Funktion von n, f(n), von einer Form, die sich wiederum von einer linearen Rekurrenz darstellen läßt. Da wir uns nur mit ganzzahligen Folgen befassen, ist c_k gleich Eins.

Eine lineare Rekurrenz ist homogen, wenn f(n) gleich Null ist.

Beispiele.

• Inhomogene lineare Rekurrenz 2.Ordnung: $\,a_{n+2}=5a_{n+1}-a_{n}-n,\qquad a_{0}=0,a_{1}=1$
• Inhomogene lineare Rekurrenz 3.Ordnung: $\,a_{n+3}=a_{n+2}+a_{n+1}+a_{n}+1,\qquad a_{0}=0,a_{1}=1,a_{2}=-1$
• Homogene lineare Rekurrenz 4.Ordnung: $\,a_{n+4}=2a_{n+3}-a_{n+2}+5a_{n+1}-a_{n},\qquad a_{0}=-5,a_{1}=-1,a_{2}=3,a_{3}=-7$
• Nichtlineare Rekurrenz ('quadratisch'): $a_{n+2}=a_{n+1}a_{n},\qquad a_{0}=2,a_{1}=3$
• Andere nichtlineare Rekurrenz: $a_{n+2}=na_{n+1}-a_{n},\qquad a_{0}=1,a_{1}=2$