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 an = (3n-
1+5)/2 für festes n voraus.
Dann ist an+1 = 3an -5
= 3(3n-1+5)/2
- 5 =
(3n + 15 -10)/2 =
(3n + 5)/2.
Diese Formel hätten wir aber auch herleiten können: Setze bn = an -5/2. Dann gilt offenbar die einfachere Rekursionsgleichung bn+1 = an+1 - 5/2 = 3an - 15/2 = 3bn und b1 = 1/2. Hier ist die Auflösung einfach: bn = 3n-1/2, und somit an = (3n-1 -5)/2.
Doch schon bei einfachsten Rekursionsgleichungen lässt sich die geschlossene Form nicht mehr raten:
Beispiel 2: Fn+2 = Fn+1 + Fn, F0 = 0, F1 = 1.
Diese Rekursionsformel bestimmt die sogenannten Fibonaccizahlen.
Binet (1843)
|