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

Aus Wikibooks

Wechseln zu: Navigation, Suche

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_ka_{n+k} = c_{k-1}a_{n+k-1} + c_{k-2}a_{n+k-2} + \cdots + c_0a_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 ci 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 ck 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
Von „http://de.wikibooks.org/wiki/Lineare_Rekurrenzen,_Potenzreihen_und_ihre_erzeugenden_Funktionen/_Homogene_und_inhomogene_Rekurrenzen“
Persönliche Werkzeuge