DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Inhalt

1. Raten der Lösung.
2. Black-Box Verfahren für gewisse Rekursionsgleichungen, ohne Begründung warum es funktionert, für diejenigen, die das 4-Schritt Verfahren nicht lesen wollen oder können.
3. Ein 4-Schritte Verfahren, sehr weit anwendbar (obwohl es auch nicht immer funktioniert), und arbeitet mit formalen Potenzreihen Die später in der Analysis benötigte Partialbruchzerlegung ist wesentlicher Bestandteil.

Definition: Für eine Folge (an) ist eine Rekursionsgleichung eine Gleichung an = f(an-1, ... ,an-k), die für beliebiges n k gilt und in der nur an, an-1, ... ,an-k, die Variable n, sowie Konstanten vorkommen.

Für jede gegebenen Anfangswerte a0, a1, ... , ak ist dann der Rest der Folge eindeutig bestimmt.

Beweis durch vollständige Induktion: ........ Beweis mittels kleinstem Verbrecher (Wohlordnung): Angenommen zwei verschiedene Folgen (an) (a'n) erfüllen die Rekursionsgleichung samt Anfangswerten. Da die Folgen verschieden sind, gibt es eine kleinste natürliche Zahl t mit at a't, und wegen der gleichen Anfangswerte ist t > k. Dann ist aber at = f(at-1, ... ,at-k) = f(a't-1, ... ,a't-k) = a't, ein Widerspruch.

an = (3n-1+5)/2.

Beweis durch Vollständige Induktion.
IA: a_1 = (1+5)/2 = 3.
IS: Wir setzen a_n = (3^{n- 1}+5)/2 für festes n voraus. Dann ist a_n+1 = 3a_n -5 = 3(3^n-1+5)/2 - 5 = (3ⁿ + 15 -10)/2 = (3ⁿ + 5)/2.

Diese Formel hätten wir aber auch herleiten können: Setze b_n = a_n -5/2. Dann gilt offenbar die einfachere Rekursionsgleichung b_n+1 = a_n+1 - 5/2 = 3a_n - 15/2 = 3b_n und b₁ = 1/2. Hier ist die Auflösung einfach: b_n = 3^n-1/2, und somit a_n = (3^n-1 -5)/2.

Doch schon bei einfachsten Rekursionsgleichungen lässt sich die geschlossene Form nicht mehr raten:

Beispiel 2: F_n+2 = F_n+1 + F_n, F₀ = 0, F₁ = 1.

Diese Rekursionsformel bestimmt die sogenannten Fibonaccizahlen.

Binet (1843) Fn = 1 5 (n - (-1)n n ), wobei = (1 + 5)/2 1.61803 der sogenannte "goldene Schnitt" ist. Beweis: