1461164200766160982400i4479124 n

Rekurencja

Mówimy, żc ciąg lest zdefiniowany rekurcncvmie. jeśli:

(P) Określony jest pewien skończony zbiór wyrazów ciągu, zazwyczaj kilka pierwszych lub pierwszy wyraz.

(R) Pozostałe wyrazy ciągu są zdefiniowane za pomocą poprzednich wyrazów ciągu. (Wzór definiujący ciąg w taki sposób nazywamy wzorem, równaniem lub zależnością rckurencyjną).

(P) - początek lub krok początkowy. (R) - reguła rckurencyjną.

Twierdzenie 1

Rozważmy zależność rckurencyjną postaci s_n = as_n-i 4- 6s_n-2-mającą równanie charakterystyczne

x² - ax - b = 0.

gdzie a i 6 są stałymi niezerowymi.

(a)    Jeśli równanie charakterystyczne ma dwa różne rozwiązania ri i r₂. to

(*)    «n=Cir^+c₂r5

dla pewnych stałych ej i c₂. Jeśli sq i Sj są dane. to wartości stałych mogą być wyznaczone przez podstawienie n — 0 i n = 1 do równania (*) i rozwiązanie układu dwóch równali z niewiadomymi ej i c₂.

(b)    Jeśli równanie charakterystyczne ma tylko jedno rozwią- | zanie r. to

(**)    s_n - Cirⁿ +C2 -7? r"

dla pewnych stałych ej i c₂. Tak jak w punkcie (a), można wyznaczyć Cj i c₂, jeśli dane są so i s\.

Uwaga! To twierdzenie stosuje się tylko do zależności reku-rcncyjnych postaci

s_n = as_n-i 4- bs„-₂.

sir N I 5