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 a und b seinen die Nullstellen der charakteristischen Gleichung t2+a1t+a2 = 0.

Falls a ¹ b, so gibt es Konstanten A,B mit un = Aan + Bbn.
Falls a = b, so gibt es Konstanten C,D mit un = (Cn+D)an.

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

Beweis durch vollständige Induktion:

(1) Falls a ¹ b, dann setzen wir A = (c1- c0b)/(a -b), B = (c1-c0 a)/(b -a).
IA: Aa0 + Bb0 = A + B = c0(a -b)/ (a -b) = c0 und Aa1 + Bb1 = Aa+ Bb = (c1a- c0ba -c1b+ c0ab)/ (a- b) = 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 an+1 + B bn+1) -a2 (Aan + Bbn) =
=
- Aan(a1 a+ a2) - Bbn (a1 b+ a2) =
=
Aa n+2 + Bbn+2,
wobei wir die Rekursionsgleichung und die Induktionsvoraussetzung einsetzen, etwas rechnen, und benutzen, daß   a2+a1 a+a2 = 0 bzw. b2+ a1b+a2 = 0.

(2) Falls a = b, dann funktioniert obiger Ansatz nicht--- wir dürfen ja nicht durch 0 teilen. Also setzen wir C = (c1- ac0 ) /a und D = c0.
IA: c0=(C*0 + D) und c1 = aC + ac0 = (C+D)a.
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)an+1 ) -a2 ((Cn+D)an) =
=
- Can (a1(n+1)a + a2n) - Dan (a1a + a2)
Nun benutzen wir die Voraussetzung der doppelten Nullstelle, t2 - 2at + a2 = (t - a)2 = t2 + a1t + a2, um a1 = - 2a sowie a2 = a2 zu folgern. Dies setzen wir in die linke Klammer obiger Gleichung ein. In der rechten Klammer wird a2+a1a +a2 = 0 benutzt:
un+2
=
- Can (-2(n+1)a2 + a2 n) + Dan+2 =
=
Ca n+2 (n+2) + Dan+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.