Lineare Differenzengleichung

Lineare Differenzengleichungen (auch lineare Rekursionsgleichungen, selten C-Rekursionen oder lineare Rekurrenz von engl. linear recurrence relation) sind Beziehungen einer besonders einfachen Form zwischen den Gliedern einer Folge.

Ein bekanntes Beispiel einer Folge, die einer linearen Differenzengleichung genügt, ist die Fibonacci-Folge. Mit der linearen Differenzengleichung

${\displaystyle f_{n}=f_{n-1}+f_{n-2}\quad (n=2,3,4,\dots )}${\displaystyle f_{n}=f_{n-1}+f_{n-2}\quad (n=2,3,4,\dots )}

und den Anfangswerten ${\displaystyle f_{0}=0}${\displaystyle f_{0}=0} und ${\displaystyle f_{1}=1}${\displaystyle f_{1}=1} ergibt sich die Folge

0, 1, 1, 2, 3, 5, 8, 13, ...

Jedes Folgenglied (abgesehen von den beiden Anfangswerten) ist also die Summe der beiden vorherigen.

Allgemein nennt man jede Gleichung der Form

${\displaystyle f_{n}=a_{1}f_{n-1}+a_{2}f_{n-2}}${\displaystyle f_{n}=a_{1}f_{n-1}+a_{2}f_{n-2}}

mit gegebenen Koeffizienten ${\displaystyle a_{1}}${\displaystyle a_{1}} und ${\displaystyle a_{2}}${\displaystyle a_{2}} eine (homogene) lineare Differenzengleichung 2. Ordnung (mit konstanten Koeffizienten). Eine Folge ${\displaystyle F=(f_{0},f_{1},f_{2},\dots ),}${\displaystyle F=(f_{0},f_{1},f_{2},\dots ),} welche die Gleichung für ${\displaystyle n=2,3,4,\dots }${\displaystyle n=2,3,4,\dots } erfüllt, heißt Lösung der Differenzengleichung. Diese Lösungen sind durch die zwei Anfangswerte eindeutig definiert.

Die Fibonacci-Folge ist also eine Lösung der Differenzengleichung, die durch ${\displaystyle a_{1}=a_{2}=1}${\displaystyle a_{1}=a_{2}=1} definiert ist. Die Folge ist durch die Anfangswerte ${\displaystyle f_{0}=0}${\displaystyle f_{0}=0} und ${\displaystyle f_{1}=1}${\displaystyle f_{1}=1} eindeutig bestimmt.

Eine lineare Differenzengleichung ${\displaystyle k}${\displaystyle k}-ter Ordnung über einem Körper ${\displaystyle \mathbb {K} }${\displaystyle \mathbb {K} } ist von der Form

${\displaystyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n),}${\displaystyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n),}

wobei ${\displaystyle a_{i}(n)\in \mathbb {K} ,a_{0}(n)\neq 0,n\in \mathbb {N} ,n\geq k}${\displaystyle a_{i}(n)\in \mathbb {K} ,a_{0}(n)\neq 0,n\in \mathbb {N} ,n\geq k}. Die lineare Differenzengleichung wird dabei von den Koeffizienten ${\displaystyle a_{0}(n),a_{1}(n),\dots ,a_{k}(n)}${\displaystyle a_{0}(n),a_{1}(n),\dots ,a_{k}(n)} und der Funktion ${\displaystyle b(n)}${\displaystyle b(n)} definiert. Eine Zahlenfolge ${\displaystyle F=(f_{0},f_{1},f_{2},\dots )}${\displaystyle F=(f_{0},f_{1},f_{2},\dots )}, die für alle ${\displaystyle n\geq k}${\displaystyle n\geq k} die Gleichung erfüllt, heißt Lösung der Differenzengleichung. Diese unendliche Folge ist durch ihre ${\displaystyle k}${\displaystyle k} Anfangswerte ${\displaystyle f_{0},f_{1},\dots ,f_{k-1}}${\displaystyle f_{0},f_{1},\dots ,f_{k-1}} eindeutig bestimmt. Ist ${\displaystyle b(n)=0}${\displaystyle b(n)=0} für alle ${\displaystyle n\geq k}${\displaystyle n\geq k}, so heißt die Gleichung homogen, ansonsten heißt sie inhomogen. Die Zahlenfolge ${\displaystyle f_{n}=0}${\displaystyle f_{n}=0} für alle ${\displaystyle n}${\displaystyle n} erfüllt alle homogenen Gleichungen und heißt deshalb triviale Lösung.

Ohne Beschränkung der Allgemeinheit kann ${\displaystyle a_{0}(n)=-1}${\displaystyle a_{0}(n)=-1} angenommen werden. Damit erhält man eine alternative Darstellung, die die Berechnungsvorschrift für ${\displaystyle f_{n}}${\displaystyle f_{n}} aus den ${\displaystyle k}${\displaystyle k} vorhergehenden Werten anschaulicher verdeutlicht:

${\displaystyle f_{n}=a_{1}(n)f_{n-1}+a_{2}(n)f_{n-2}+\dots +a_{k}(n)f_{n-k}-b(n)=\sum _{i=1}^{k}a_{i}(n)f_{n-i}-b(n),}${\displaystyle f_{n}=a_{1}(n)f_{n-1}+a_{2}(n)f_{n-2}+\dots +a_{k}(n)f_{n-k}-b(n)=\sum _{i=1}^{k}a_{i}(n)f_{n-i}-b(n),}

wobei ${\displaystyle a_{i}(n)\in \mathbb {K} ,n\in \mathbb {N} ,n\geq k}${\displaystyle a_{i}(n)\in \mathbb {K} ,n\in \mathbb {N} ,n\geq k}.

• Sind ${\displaystyle F}${\displaystyle F} und ${\displaystyle G}${\displaystyle G} Lösungen der homogenen linearen Differenzengleichung ${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=0}${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=0}, dann ist auch ${\displaystyle \alpha F+\beta G}${\displaystyle \alpha F+\beta G} für beliebige ${\displaystyle \alpha ,\beta \in \mathbb {K} }${\displaystyle \alpha ,\beta \in \mathbb {K} } eine Lösung.
• Sind ${\displaystyle F}${\displaystyle F} und ${\displaystyle G}${\displaystyle G} Lösungen der inhomogenen linearen Differenzengleichung ${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n)}${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n)}, dann ist ${\displaystyle F-G}${\displaystyle F-G} eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit ${\displaystyle b(n)=0}${\displaystyle b(n)=0} für alle ${\displaystyle n\geq k}${\displaystyle n\geq k}.
• Ist ${\displaystyle F}${\displaystyle F} eine Lösung der inhomogenen linearen Differenzengleichung ${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n)}${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}(n)f_{n-i}=b(n)} und ${\displaystyle G}${\displaystyle G} eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit ${\displaystyle b(n)=0}${\displaystyle b(n)=0} für alle ${\displaystyle n\geq k}${\displaystyle n\geq k}, dann ist auch ${\displaystyle F+\alpha G}${\displaystyle F+\alpha G} für beliebige ${\displaystyle \alpha \in \mathbb {K} }${\displaystyle \alpha \in \mathbb {K} } eine Lösung der inhomogenen linearen Differenzengleichung.

Die erste Idee zur Lösung besteht in der Beobachtung, dass derartige Folgen meist exponentiell wachsen. Das legt den ersten Ansatz ${\displaystyle f_{n}=\lambda ^{n}}${\displaystyle f_{n}=\lambda ^{n}} mit einem festen ${\displaystyle \lambda \in \mathbb {K} }${\displaystyle \lambda \in \mathbb {K} } nahe. Eingesetzt ergibt das

${\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+a_{2}\lambda ^{n-2}\quad (n=2,3,4,\dots ),}${\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+a_{2}\lambda ^{n-2}\quad (n=2,3,4,\dots ),}

d. h.

${\displaystyle \lambda ^{2}-a_{1}\lambda -a_{2}=0.}${\displaystyle \lambda ^{2}-a_{1}\lambda -a_{2}=0.}

Diese quadratische Gleichung heißt charakteristische Gleichung der Rekursion. Folgen der Form ${\displaystyle f_{n}=\lambda ^{n}}${\displaystyle f_{n}=\lambda ^{n}} mit einem ${\displaystyle \lambda }${\displaystyle \lambda }, das Lösung der charakteristischen Gleichung ist, erfüllen also die gewünschte Rekursionsgleichung.

Die zweite Idee ist die der Superposition: Sind ${\displaystyle F}${\displaystyle F} und ${\displaystyle G}${\displaystyle G} Folgen, die die Rekursionsgleichung erfüllen, so gilt das auch für die Folge ${\displaystyle H}${\displaystyle H} mit

${\displaystyle h_{n}=c_{1}f_{n}+c_{2}g_{n}}${\displaystyle h_{n}=c_{1}f_{n}+c_{2}g_{n}}

mit beliebigen Konstanten ${\displaystyle c_{1},c_{2}\in \mathbb {K} }${\displaystyle c_{1},c_{2}\in \mathbb {K} }. Man kann das auch so ausdrücken: Die Menge aller Folgen, die die Rekursionsgleichung erfüllen, bildet einen Vektorraum über ${\displaystyle \mathbb {K} }${\displaystyle \mathbb {K} }.

Sind jetzt Anfangswerte ${\displaystyle f_{0},f_{1}}${\displaystyle f_{0},f_{1}} gegeben, und hat die charakteristische Gleichung zwei verschiedene Lösungen ${\displaystyle \lambda _{1},\lambda _{2}}${\displaystyle \lambda _{1},\lambda _{2}}, so können die Koeffizienten ${\displaystyle c_{1},c_{2}}${\displaystyle c_{1},c_{2}} aus dem folgenden linearen Gleichungssystem bestimmt werden:

${\displaystyle f_{0}=c_{1}\lambda _{1}^{0}+c_{2}\lambda _{2}^{0}=c_{1}+c_{2}}${\displaystyle f_{0}=c_{1}\lambda _{1}^{0}+c_{2}\lambda _{2}^{0}=c_{1}+c_{2}}

${\displaystyle f_{1}=c_{1}\lambda _{1}^{1}+c_{2}\lambda _{2}^{1}=c_{1}\lambda _{1}+c_{2}\lambda _{2}}${\displaystyle f_{1}=c_{1}\lambda _{1}^{1}+c_{2}\lambda _{2}^{1}=c_{1}\lambda _{1}+c_{2}\lambda _{2}}

Dann gilt ${\displaystyle f_{n}=c_{1}\lambda _{1}^{n}+c_{2}\lambda _{2}^{n}}${\displaystyle f_{n}=c_{1}\lambda _{1}^{n}+c_{2}\lambda _{2}^{n}} für alle ${\displaystyle n}${\displaystyle n}.

Im Beispiel der Fibonacci-Folge sind

${\displaystyle \lambda _{1/2}={\frac {1\pm {\sqrt {5}}}{2}},\quad c_{1}={\frac {1}{\sqrt {5}}}=-c_{2},}${\displaystyle \lambda _{1/2}={\frac {1\pm {\sqrt {5}}}{2}},\quad c_{1}={\frac {1}{\sqrt {5}}}=-c_{2},}

es ergibt sich also die sogenannte Binet-Formel

${\displaystyle f_{n}={\frac {1}{\sqrt {5}}}(\lambda _{1}^{n}-\lambda _{2}^{n}).}${\displaystyle f_{n}={\frac {1}{\sqrt {5}}}(\lambda _{1}^{n}-\lambda _{2}^{n}).}

Hat die charakteristische Gleichung nur eine Lösung, das heißt eine doppelte Nullstelle ${\displaystyle \lambda ,}${\displaystyle \lambda ,} so wird die homogene Differenzengleichung auch von der Folge ${\displaystyle {\big (}n\lambda ^{n-1}{\big )}}${\displaystyle {\big (}n\lambda ^{n-1}{\big )}} gelöst (diese beginnt mit ${\displaystyle 0\lambda ^{-1}=0,}${\displaystyle 0\lambda ^{-1}=0,} was für ${\displaystyle \lambda =0}${\displaystyle \lambda =0} noch so festgelegt sei). Die allgemeine Lösung hat die Form

${\displaystyle f_{n}=c_{1}\lambda ^{n}+c_{2}n\lambda ^{n-1}.}${\displaystyle f_{n}=c_{1}\lambda ^{n}+c_{2}n\lambda ^{n-1}.}

Beispielsweise erfüllt ${\displaystyle f_{n}=n}${\displaystyle f_{n}=n} (also ${\displaystyle c_{1}=0,c_{2}=1,\lambda =1}${\displaystyle c_{1}=0,c_{2}=1,\lambda =1}) die Rekursionsgleichung

${\displaystyle f_{n}=2f_{n-1}-f_{n-2}.}${\displaystyle f_{n}=2f_{n-1}-f_{n-2}.}

Eine lineare Differenzengleichung mit konstanten Koeffizienten hat die Form

${\displaystyle \sum _{i=0}^{k}a_{i}f_{n-i}=b(n),}${\displaystyle \sum _{i=0}^{k}a_{i}f_{n-i}=b(n),}

wobei alle ${\displaystyle a_{i}}${\displaystyle a_{i}} konstant sind.

Mit dem Ansatz ${\displaystyle f_{n}=\lambda ^{n}}${\displaystyle f_{n}=\lambda ^{n}} wird eine nichttriviale Lösung der homogenen Gleichung ${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}f_{n-i}=0}${\displaystyle \textstyle \sum _{i=0}^{k}a_{i}f_{n-i}=0} ermittelt. ${\displaystyle a_{0}}${\displaystyle a_{0}} sei o. B. d. A. gleich ${\displaystyle -1}${\displaystyle -1}. Dies führt auf die charakteristische Gleichung ${\displaystyle \textstyle \lambda ^{n}-\sum _{i=1}^{k}a_{i}\lambda ^{n-i}=0}${\displaystyle \textstyle \lambda ^{n}-\sum _{i=1}^{k}a_{i}\lambda ^{n-i}=0}. Die verschiedenen Nullstellen der Gleichung ergeben dann linear unabhängige Lösungsfolgen und damit Lösungen der homogenen Gleichung.

Sind die Nullstellen nicht verschieden, so kommt die zu einer mehrfachen Nullstelle gehörende Lösungsfolge mit einem Faktor in der Lösung vor, der ein Polynom in ${\displaystyle n}${\displaystyle n} mit einem Grad kleiner als die Vielfachheit der Nullstelle ist.

Beispiel:

Die Bestimmung geschieht hier analog zu Differentialgleichungen.

In der letzten Zeile wird ${\displaystyle \mathbb {K} =\mathbb {R} }${\displaystyle \mathbb {K} =\mathbb {R} } angenommen. Falls der Ansatz bereits eine Lösung der zugehörigen homogenen Differenzengleichung sein sollte, ist er mit ${\displaystyle n,n^{2},n^{3}}${\displaystyle n,n^{2},n^{3}} zu multiplizieren, bis er eine Lösung der inhomogenen Gleichung liefert.

Gegeben ist eine Folge ${\displaystyle F}${\displaystyle F} mit ${\displaystyle f_{0}=2,\quad f_{1}=5,\quad f_{n}=5f_{n-1}-6f_{n-2}+(n-2)}${\displaystyle f_{0}=2,\quad f_{1}=5,\quad f_{n}=5f_{n-1}-6f_{n-2}+(n-2)}. Gesucht ist die explizite Formel. Wir suchen zuerst die allgemeine Lösung für die homogene Rekursionsgleichung.

Nun suchen wir eine spezielle Lösung der inhomogenen Rekursionsgleichung, die partikuläre Lösung.

${\displaystyle c_{3}n+c_{4}-5(c_{3}(n-1)+c_{4})+6(c_{3}(n-2)+c_{4})=n-2}${\displaystyle c_{3}n+c_{4}-5(c_{3}(n-1)+c_{4})+6(c_{3}(n-2)+c_{4})=n-2}

Gemäß den obigen Rechenregeln erhalten wir mit ${\displaystyle \textstyle f_{n}=f_{\mathrm {homogen} ,n}+f_{\mathrm {partikulaer} ,n}=c_{1}\cdot 2^{n}+c_{2}\cdot 3^{n}+{\frac {1}{2}}n+{\frac {3}{4}}}${\displaystyle \textstyle f_{n}=f_{\mathrm {homogen} ,n}+f_{\mathrm {partikulaer} ,n}=c_{1}\cdot 2^{n}+c_{2}\cdot 3^{n}+{\frac {1}{2}}n+{\frac {3}{4}}} alle Lösungen der inhomogenen Rekursionsgleichung. Nun müssen ${\displaystyle c_{1}}${\displaystyle c_{1}} und ${\displaystyle c_{2}}${\displaystyle c_{2}} noch so bestimmt werden, dass ${\displaystyle f_{0}=2}${\displaystyle f_{0}=2} und ${\displaystyle f_{1}=5}${\displaystyle f_{1}=5} gilt.

Also ist ${\displaystyle \textstyle f_{n}={\frac {5}{4}}\cdot 3^{n}+{\frac {1}{2}}\cdot n+{\frac {3}{4}}}${\displaystyle \textstyle f_{n}={\frac {5}{4}}\cdot 3^{n}+{\frac {1}{2}}\cdot n+{\frac {3}{4}}} die gesuchte Formel.

• Inhomogene lineare Differentialgleichung
• Erzeugende Funktion
• Gewöhnliche Differentialgleichung

• L. Berg: Lineare Gleichungssysteme mit Bandstruktur. Carl Hanser, München/Wien 1986.
• Ian Jaques: Mathematics for Economics and Business. Fifth Edition, Prentice Hall, 2006 (Kapitel 9.1 Difference Equations).

• Folgen und Reihen