Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Verfahren für Rekursionsgleichungen vom Typ
un+2 + a1un+1 + a2un = 0

Die vorgestellte Methode wird (natürlich) bewiesen. Falls Sie aber verstehen wollen, wie man auf die Formel kommt, gehen Sie besser gleich zur 4-Schritt Methode.

Die Folge (un) sei durch die Rekursionsgleichung
un+2 + a1un+1+ a2un = 0
mit Anfangswerten u0 = c0, u1 = c1, definiert.
Die komplexen Zahlen x und y seinen die Nullstellen der charakteristischen Gleichung t2+a1t+a2 = 0.

Falls x y, so gibt es Konstanten A,B mit un = Axn + Byn.
Falls x = y, so gibt es Konstanten C,D mit un = (Cn+D)xn.

Dabei sind die Konstanten A, B (bzw. C, D) durch die Anfangswerte c0, c1 bestimmt.

Beweis durch vollständige Induktion:

(1) Falls x y, dann setzen wir A = (c1- c0y)/(x -y), B = (c1-c0 x)/(y -x).
IA: Ax0 + By0 = A + B = c0(x -y)/ (x -y) = c0 und Ax1 + By1 = Ax+ By = (c1x- c0yx -c1y+ c0xy)/ (x- y) = c1.
IS: Für n 0 sei das Resultat für alle (!) ur mit 0 r n+1 gültig. Wir erhalten

un+2
=
- a1un+1 - a2un =
=
-a1(A xn+1 + B yn+1) -a2 (Axn + Byn) =
=
- Axn(a1 x+ a2) - Byn (a1 y+ a2) =
=
Ax n+2 + Byn+2,
wobei wir die Rekursionsgleichung und die Induktionsvoraussetzung einsetzen, etwas rechnen, und benutzen, daß   x2+a1x+a2 = 0 bzw. y2+ a1y+a2 = 0.

(2) Falls x= y, dann funktioniert obiger Ansatz nicht--- wir dürfen ja nicht durch 0 teilen. Also setzen wir C = (c1- xc0 )/x und D = c0.
IA: c0=(C*0 + D) und c1 = xC + xc0 = (C+D)x.
IS: Für n 0 gelte das Resultat für alle ur mit 0 r n+1. Dann folgt ebenso

un+2
=
- a1un+1 - a2un =
=
-a1( (C(n+1)+D)xn+1 ) -a2 ((Cn+D)xn) =
=
- Cxn (a1(n+1)x+ a2n) - Dxn (a1x+ a2)
Nun benutzen wir die Voraussetzung der doppelten Nullstelle, t2 - 2xt + x2 = (t - x)2 = t2 + a1t + a2, um a1 = - 2x sowie a2 = x2 zu folgern. Dies setzen wir in die linke Klammer obiger Gleichung ein. In der rechten Klammer wird x2+a1x +a2 = 0 benutzt:
un+2
=
- Cxn (-2(n+1)x2 + x2 n) + Dxn+2 =
=
Cx n+2 (n+2) + Dxn+2,
wie gewünscht.
Die Darstellung lehnt sich and Biggs, S. 250 ff an.
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.