Jak definiować ciągi rekurencyjne?

Tytułowa rekurencja jest jednym z podstawowych pojęć w informatyce, które umożliwia definiowanie ciągów różnych obiektów, pozwalając odwoływać się w definicji danego obiektu do jego poprzedników. Pokażemy dwie klasy takich definicji i omówimy ich równoważność.

Zacznijmy od prostych przykładów: ciągu arytmetycznego i ciągu geometrycznego. Rozważmy dwa ciągi $a0,a1,...$ i $|b0,b1,...$ zadane przez

a0 = 1,an+1 = an + 3 b0 = 1,bn+1 = 2⋅bn.

(Takie ciągi przydają się, na przykład, do szacowania, jak długo działa program, który rekurencyjnie wywołuje siebie lub inne programy.)

W obu przypadkach, żeby poznać wartość konkretnego $a n$ lub $b n$ (korzystając wprost z definicji), trzeba się wciąż odwoływać do wartości poprzednich elementów, aż dojdziemy do pierwszego elementu $(a0$ lub $|b0).$ Oczywiście, $an$ jest ciągiem arytmetycznym, a $|bn$ ciągiem geometrycznym, więc wiemy, że procedurę obliczania wartości konkretnego elementu ciągu da się przyspieszyć i skorzystać ze wzorów: $an = 3n+ 1$ oraz $|bn = 2n.$ Nie zawsze jest to takie proste. Trochę ciekawszym przykładem jest ciąg Fibonacciego zadany przez:

F0 = 0,F1 = 1,Fn+2 = Fn+1 + Fn.

Zauważmy, że aby obliczyć wartości kolejnych elementów ciągu, musimy się zawsze odwołać do dwóch poprzednich elementów i dlatego potrzebne są aż dwa początkowe elementy. Spróbujmy uogólnić to zjawisko i zdefiniować tak zwane liniowe ciągi rekurencyjne, którym będziemy się dalej szerzej przyglądać. Powiemy, że ciąg $c0,c1,...$ jest liniowym ciągiem rekurencyjnym stopnia $k,$ jeśli znamy wartości pierwszych $|k$ elementów, a pozostałe elementy są wyznaczone przez $k$ poprzednich elementów. Dokładniej:

c = s,c = s ,...,c = s ,c = r ⋅c +...+ r ⋅c , 0 0 1 1 k−1 k−1 n+k k−1 n+k− 1 0 n

(1)

dla danych liczb rzeczywistych $s0...,sk− 1,r0,...rk−1.$ Dodatkowo zakładamy, że $r0 ≠0$ (inaczej ciąg byłby stopnia $|k− 1$ ). Przykładowo ciąg $(bn)$ jest takim ciągiem stopnia 1 i podobnie $(F ) n$ jest takim ciągiem stopnia 2. Ciąg $|(an)$ nie spełnia tej definicji, ponieważ $an+1$ odwołuje się do stałej $|3$ (zauważmy, że w definicji (1) stałe $|ri$ mogą być tylko przemnożone przez jeden z poprzednich elementów ciągu $cn+i$ ). Można to jednak łatwo naprawić: zauważmy, że ciąg $|(a ) n$ spełnia $a − a = 3. n n−1$ Tak więc wystarczy w definicji podmienić trójkę na $(an −an−1).$ Otrzymujemy w ten sposób równoważną rekurencję stopnia 2:

a0 = 1,a1 = 4,an+1 = 2⋅an − an−1.

Pierwsze pytanie, jakim się zajmiemy w tym tekście, to pytanie, czy możemy ograniczyć się wyłącznie do ciągów stopnia 1. Okazuje się, że odpowiedź brzmi "tak", ale - niestety - nie za darmo. Jeśli pozwolimy na to, żeby użyć więcej niż jednego ciągu, to każdy ciąg stopnia $|k$ można zamienić na układ $|k$ ciągów stopnia 1. Przykładowo ciąg Fibonacciego można zdefiniować, używając jednego dodatkowego ciągu:

⎧⎪F = 0,F = F + G n ⎪⎨ 0 n+1 n 0=1,Gn+1=Fn. ⎪⎪⎩G

Nietrudno zauważyć, że ciąg $n) |(G$ służy jako bufor do przetrzymywania wartości $F n−1$ i równie nietrudno uogólnić tę metodę na dowolny ciąg stopnia $|k.$ W takim razie zadajmy pytanie odwrotne: czy mając układ $|k$ ciągów stopnia 1, możemy zdefiniować każdy ciąg z tego układu za pomocą jednego ciągu (być może stopnia większego niż 1)? Rozważmy przykład, który pokaże trudność tego zadania: zdefiniujemy ciąg $2 |dn = n ,$ używając dwóch dodatkowych ciągów: $en = n$ i $fn = 1$

⎧ ⎪⎪⎪⎪d0 = 0,dn+1 = dn +2 ⋅en + fn, ⎪⎨e0 = 0,en+1 = en + fn, ⎪⎪⎪ ⎪⎪⎩ f0 = 1, fn+1 = fn.

(2)

Poprawność tej definicji wynika z prostej tożsamości $(n + 1)2 = n2 + 2n + 1.$ Czy możemy zdefiniować ciąg $|(dn)$ bez użycia dodatkowych ciągów? Warto się chwilę zastanowić nad tym pytaniem, zanim przeczytamy rozwiązanie. Odpowiedź brzmi "tak" i realizuje ją rekurencja poniżej:

d = 0,d = 1,d = 4, d = 3⋅d − 3 ⋅d + d . 0 1 2 n+3 n+2 n+1 n

(3)

Szybkie rachunki pokazują poprawność tego wzoru

3⋅(n + 2)2− 3⋅(n + 1)2 +n2 = n2 +6n + 9 = (n + 3)2.

(4)

Ogólnie prawdą jest, że każdy ciąg zdefiniowany za pomocą układu $| k$ ciągów stopnia 1 możemy przekształcić w ciąg zdefiniowany za pomocą tylko jednego ciągu o stopniu $k.$ Dowód tego faktu nie jest bardzo trudny, ale wymaga podstawowej znajomości algebry liniowej, więc nie omówimy go tutaj w pełnej ogólności.

Zamiast tego spróbujemy zademonstrować tę własność dla szczególnego przypadku. Zauważmy, że nietrudno uogólnić definicję (2) tak, żeby zdefiniować $| k dn = n$ dla dowolnego $| k.$ Wystarczy rozpisać wzór na $k |(n+ 1)$ i użyć $k$ dodatkowych ciągów. Wykażemy, że można ten ciąg zdefiniować, używając tylko jednego ciągu stopnia $|k+ 1.$ Pierwsze $|k+ 1$ elementów zadajemy w oczywisty sposób jako:

k k d0 = 0,...,dk−1 = (k − 1) ,dk = k .

Rekurencję weźmiemy trochę "z kapelusza". Najpierw rozwiniemy wielomian w równaniu $|(x− 1)k+1 = 0$ :

k+1 k+1 k + 1 i k+1− i (x − 1) = Q ( i )( −1) ⋅x = 0; i 0

(5)

i przeniesiemy wszystkie wyrazy o stopniu mniejszym niż $k +1$ na prawą stronę

k+1 k+ 1 xk+1 = Q ( )(−1)i+1⋅xk+1− i. i 1 i

(6)

Z tego wzoru magicznie otrzymujemy wzór rekurencyjny na $d , n$ podstawiając $|dn+i$ pod jednomian $i x$ dla każdego $0 ⩽ i⩽ k+ 1$ (w szczególności pod $|x0$ podstawiamy $|dn$ ):

k+1 k + 1 dn+k+1 =Q ( )( −1)i+1⋅dn+1−i. i 1 i

Sprawdźmy, że dla $k = 2$ dostajemy $dn+3 = 3 ⋅dn+2− 3⋅dn+1 + dn,$ czyli dokładnie rozwiązanie z (3). Pozostaje wykazać, że rekurencja otrzymana z (6) jest poprawna dla każdego $|k.$ Wystarczy sprawdzić, że

k+1 (n+ k + 1)k = Q (k + 1)(−1)i+1 ⋅(n + k +1 −i)k, i 1 i

czyli

k+1 k + 1 i k Q ( )(−1) ⋅(n +k + 1− i) = 0. i 0 i

(7)

Uzasadnimy to równanie, korzystając z metody interpretacji kombinatorycznej. Otóż dla ustalonej wartości $i$ rozważmy $(k+1)(−1)i⋅(n +k + 1− i)k. i$ Przyjmijmy, że mamy dwie grupy elementów: pierwszą grupę $1, |G$ gdzie $1 =k+1 G$ ; i drugą $2, G$ gdzie $2 =n. G$ Możemy zinterpretować $k+1 ( i )$ jako wybranie podzbioru $1 |A$ o rozmiarze $i,$ natomiast $(n + k +1 −i)k$ jako dobranie ciągu z powtórzeniami $(e ,e ,...,e) 1 2 k$ spośród pozostałych elementów, czyli $2∪(G1∖A). ei∈ G$ Pozostały czynnik $i |(−1)$ określa, czy to wszystko dodamy, czy odejmiemy od całej sumy.

Obliczymy teraz to samo raz jeszcze, ale tym razem w innej kolejności. Ustalmy najpierw jakiś ciąg z powtórzeniami $(e1,e2,...,ek),$ gdzie $1∪G2.ei∈G$ Niech $1 S ⊆ G$ będzie zbiorem elementów, które nie występują w ciągu $|(e,e ,...,e ) 1 2 k$ i oznaczmy $m$ Pytanie brzmi, na ile różnych sposobów można dobrać do tego ciągu zbiór $A$ tak, żeby otrzymać dokładnie to samo co poprzednio. Jedyny warunek, jaki $A |$ musi spełniać, to $|A$ Przyjmijmy dodatkowo, że chcemy wybrać $A$ ustalonego rozmiaru $|i.$ Możemy to zrobić na $|(m) i$ sposobów i wtedy będziemy brali ten składnik ze znakiem $i (− 1) .$ To znaczy, że dla ustalonego ciągu $|(e1,e2,...,ek)$ dodamy do sumy $m m |P i 0( i)( −1)i.$ Podstawiając w (5) $|m$ oraz $x = 1,$ widzimy, że to wyrażenie jest zawsze równe $|0.$ To znaczy, że sumując po wszystkich ciągach $(e ,e,...,e ), 1 2 k$ otrzymamy i tak $|0,$ czyli wykazaliśmy (7).

Nasz argument, niestety, wymagał wyczarowania rekurencji otrzymanej z rozpisania (5). Żeby otrzymać ten wzór bez zgadywania, potrzeba ponownie nieco algebry liniowej. Co więcej, zauważmy, że nawet samo udowodnienie poprawności tego wzoru wymagało znajomości podstaw kombinatoryki. Niech będzie to więc przestroga, że i informatykowi dobrze jest znać trochę matematyki.