Liniowe równania rekurencyjne zadane wielonormowo

Wpis ten będzie dotyczyć równań rekurencyjnych, które są zadane kilkoma liniowymi wzorami, różnymi w zależności od reszty z dzielenie przez ustaloną liczbę, np.

\left\{ \begin{array}{ll} a_0&=\frac{1}{2} \\ a_{2n}&=3a_n +5\\ a_{2n+1}&=\sqrt{3} a_n+4\\ \end{array}\right.

gdzie czynniki liniowe i wyrazy wolne są stałymi jak również, gdzie mogą być zmienne, np. ciąg Rudina-Shapiro

\left\{ \begin{array}{ll} a_0&=1 \\ a_{2n}&=a_n \\ a_{2n+1}&=(-1)^n a_n\\ \end{array}\right. .

Najogólniejsza postać równania, jakie omówię we wpisie, jest następująca. Dana jest liczba naturalna L \in \mathbb{N} większa od jedynki (ona wyznacza ilość różnych wzorów), dla różnych reszt r przy dzieleniu przez L dane są ciągi \alpha_n(r) po n=1,2,3 \dots oraz \beta_n(r) dla n=0,1,2 \dots. Wtedy dla n\geq 1 przyjmujemy

z(Ln+r)=\alpha_n(r)\cdot z(n) +\beta_n(r)

natomiast wyrazy początkowe to z(r)=\beta_0(r). Mamy zatem dla różnych reszt różne współczynniki liniowe alfa oraz beta, które dodatkowo są zmienne – zależą od n. Dodatkowo zerowe współczynniki beta pełnią rolę wyrazów początkowych.

Jest postać możliwe najbardziej ogólna, jeśli chodzi o współczynniki, natomiast jeśli chodzi o równanie – to jest to postać szczególna, gdyż we wzorze zawsze wyraz o indeksie Ln+r zależy tylko od liniowo przekształconego wyrazu o indeksie  n i żadnego innego. Tego ograniczenia nie przeskoczę w tym wpisie (ani być może w żadnym innym, ale tego nigdy nie wiadomo). Dla takiego równania znajdziemy rozwiązanie, jednak zanim dojdziemy do postaci ogólnej rozważymy po drodze prostsze sytuacje.

Zacznijmy od następującego problemu:

Przykład 1.

Jaką zależność rekurencyjną spełnia poniższy ciąg?

0, 2,2^3,2^3+2,2^5,2^5+2,2^5+2^3,2^5+2^3+2,2^7,2^7+2, \dots

Jest to uporządkowany rosnąco ciąg różnych nieparzystych potęg dwójki. Zauważmy, że możemy go opisać przy pomocy funkcji, która zależy od rozwinięć w systemie dwójkowym liczb. Mianowicie gdy \displaystyle n=\sum_{i=0}^N c_i2^i, gdzie c_i to cyfry, a N długość liczby n, to zdefiniujemy

\displaystyle z(n)=z((c_N\dots c_1c_0)_{(2)})=\sum_{i=0}^N c_i 2^{2i+1}=\sum_{i=0}^N 2 \cdot c_i4^i =2 \cdot (c_N\dots c_1c_0)_{(4)}

Widać, że są to sumy różnych parzystych potęg, dodatkowo, pewnej liczbie zapisanej w systemie dwójkowym przypisujemy dwukrotność innej, o takich samych cyfrach w systemie czwórkowym. Stąd jeśli

(c_{N_1}\dots c_1c_0)_{(2)} < (d_{N_2}\dots d_1d_0)_{(2)},

to także

2\cdot(c_{N_1}\dots c_1c_0)_{(4)} < 2\cdot (d_{N_2}\dots d_1d_0)_{(4)}.

Zatem uporządkowanie z jest rzeczywiście rosnące, łatwo też wykazać, że wyczerpuje wszystkie możliwe sumy nieparzystych potęg. Jednak skupmy się na tym, co najważniejsze, czyli zależności rekurencyjnej. Weźmy dowolną liczbę naturalną 2n+r, gdzie r=0 lub r=1. Załóżmy, że przedstawia się ona w systemie dwójkowym następująco

\displaystyle 2n+r=\sum_{i=0}^N c_i2^i.

W szczególności c_0=r oraz \displaystyle n=\sum_{i=1}^N c_i2^{i-1} – sumujemy od jedynki, a to oznacza, że potęgi są nieujemne, więc to przedstawienie jest poprawne. Zatem

\displaystyle z(n)=\sum_{i=1}^N 2c_i 4^{i-1}

ale wtedy również.

\displaystyle z(2n+r)=\sum_{i=0}^N 2c_i4^i=4\sum_{i=1}^N2c_i 4^{i-1}+2c_0=4z(n)+2r.

Zatem uzyskaliśmy

\left\{ \begin{array}{ll} z(0)&=0 \\ z(1)&=2 \\ z(2n)&=4z(n) \\ z(2n+1)&=4z(n)+2 \end{array} \right.

Idea więc jest taka, żeby rozwiązania równań szukać, licząc w systemie liczbowym odpowiedniej podstawie. Zauważmy, że mamy zgodność początkowych wyrazów z wyrazami wolnymi, oraz współczynnik przez który mnożymy z(n) jest taki sam w obu przypadkach. Można ten przykład łatwo uogólnić.

Twierdzenie 1.

Weźmy L \in \mathbb{N}_2, dowolne liczby \alpha\neq 0, \beta(0), \beta(1), \dots \beta(L-1) oraz rozważmy równanie rekurencyjne.
\left\{ \begin{array}{lll} z(r)&=\beta(r) & \mbox{dla } r=0,1, \dots L-1\\ z(Ln+r)&=\alpha z(n) + \beta(r)& \mbox{dla } r=0,1\dots L-1; n>0\end{array} \right.

Wtedy dla dowolnej liczby naturalnej \displaystyle n=\sum_{i=0}^Nc_i L^i przedstawionej w systemie pozycyjnym o podstawie L mamy wzór

\displaystyle z(c_N\dots c_1 c_0)=z\left(\sum_{i=0}^N c_iL^i\right)=\sum_{i=0}^N \beta(c_i) \alpha^i

Przed dowodem, krótki komentarz. Sposób na zapamiętanie wzoru jest taki, że cyfry zamieniają się na odpowiednie liczby \beta a L na \alpha. Wzór ten jest czymś w rodzaju transformacji między systemami liczbowymi, przynajmniej wtedy, kiedy można o tym mówić jak w pierwszym przykładzie.

Jeszcze taka uwaga. N w powyższym wzorze to minimalna potęga L potrzebna do zapisania liczby, tzn. w szczególności c_{N+k}=0 dla k>0 oraz przy rozwijaniu niezerowej liczby mamy zawsze c_N\neq 0. Powyższy wzór należy rozumieć w ten sposób, że zależy od N i zawsze sumujemy do N, nawet gdybyśmy dopisali zera po lewej. Ta sama uwaga będzie tyczyć się następnych wzorów.

Dowód.

Oznaczmy kandydata na rozwiązanie

\displaystyle \hat{z}(c_N\dots c_1c_0)=\sum_{i=0}^N \beta(c_i) \alpha^i.

Wystarczy wykazać, że \hat{z} spełnia tę samą definicję rekurencyjną oraz te same warunki początkowe co z.

Zauważmy, że dla c=0,1, \dots L-1 mamy \hat{z}(c)=\beta(c). Zatem spełnione są warunki początkowe.  Rozważmy teraz \displaystyle L \leq Ln+r=\sum_{i=0}^N c_i L^i. Wtedy oczywiście c_0=r oraz \displaystyle n=\sum_{i=1}^N c_i L^{i-1}. Policzmy

\displaystyle \hat{z}(n)=\sum_{i=1}^N \beta{c_i} \alpha^{i-1}

ale również

\displaystyle \hat{z}(Ln+r)=\sum_{i=0}^N \beta(c_i) \alpha ^i= \alpha \sum_{i=1}^N \beta( c_i) \alpha^{i-1} + \beta(c_0)=\alpha \hat{z}(n) + \beta(r).

Zatem w definiuje ta sama zależność rekurencyjna. Stąd i z równości dla wyrazów początkowych (oraz z twierdzenia o definiowaniu indukcyjnym) \hat{z}(n)=z(n) dla dowolnego naturalnego n. qed

Zastosujmy teraz wzór do rozwiązania kilku problemów.

Przykład 2.

Zobaczmy co się dzieje w  prostych sytacjach, pozostając przy ogólnym L. Najpierw  przyjmijmy \alpha=1 oraz \beta(r)=r. Oznaczmy s_L(n)=z(n). Wtedy

s_L(Ln+r)=s_L(n)+r  oraz s_L(r)=r

Jednocześnie

\displaystyle s_L(c_N\dots c_1 c_0)= \sum_{i=0}^N c_i

Zatem s_L(n) jest sumą cyfr liczby n w rozwinięciu przy podstawie L.

Przykład 3.

Przyjmijmy teraz ponownie \alpha =1, ale \beta(r)=1. Wtedy

z(Ln+r)=z(n)+1

i korzystając ze wzoru na rozwiązanie mamy

\displaystyle z(c_N\dots c_1 c_0)=\sum_{i=0}^N 1\cdot 1^i=N+1

zatem, w tym przypadku, z(n) zwraca minimalną ilość cyfr potrzebną do zapisu n w systemie o podstawie L. Możemy też stąd wyznaczyć równanie na N, które to u mnie nazywa się długością liczby. Przyjmijmy dla każdego n

N(n)=z(n)-1.

Zatem N spełnia równanie dla n>0

N(Ln+r)=z(Ln+r)-1=z(n)=N(n)+1

zaś gdy n=0

N(r)=z(r)-1=0

Czyli N spełnia tę samą zależność rekurencyjną co z, ale różni się wyrazami początkowymi.

Dodatkowo dla 0<n=c_N\dots c_1 c_0 zachodzi

\displaystyle L^N \leq \sum_{i=0}^N c_i L^i < L^{N+1}

A stąd logarytmując

N\leq \log_L n < N+1.

Zatem N=[log_L n]. Oznacza to, że rozwiązaniem rekurencji opisującej N jest właśnie część całkowita z logarytmu przy odpowiedniej podstawie.

Przykład 4.

Rozważmy dosyć prosto wyglądające równanie.

\left\{ \begin{array}{ll} a_0&=1 \\ a_1 &=0\\ a_{2n}&=2a_n +1\\ a_{2n+1}&=2 a_n+0\\ \end{array}\right.

Zauważmy, że spełnia założenia Twierdzenia 1. z podstawą systemu L=2, czynnikiem liniowym \alpha=2 i wyrazami wolnymi \beta(i)=1-i. Zatem gdy \displaystyle n=\sum_{i=0}^N c_i2^i, to

\displaystyle a(n)=(c_N\dots c_1c_0)=\sum_{i=0}^N(1-c_i)2^i

Ciąg ten więc przypisuje liczbie przedstawionej w systemie dwójkowym jej dopełnienie binarne, czyli zamienia jedynki na zera i zera na jedynki. Możemy pociągnąć obliczenia dalej.

\displaystyle a(n)=\sum_{i=0}^N(1-c_i)2^i=\sum_{i=0}^N2^i+\sum_{i=0}^Nc_i2^i=2^{N+1}-1-n

ale dla n>0 mamy równość N=[ \log_2 n ]. Zatem ostatecznie dla n>0 mamy

a_n=2^{[\log_2 n]+1}-(n+1)

oraz a_0=1.

Oczywiście przykład ten można komplikować, np. biorąc dowolne naturalne L>1 oraz \alpha = L i \beta(i)=C-i, gdzie C to jakaś stała, efekt będzie podobny.

Jako wniosek z postaci rozwiązania zauważmy jeszcze pewną rzecz, która otrzymujemy dzięki wiedzy o systemach liczbowych.

Wniosek.

Dane niech będzie równanie

\left\{ \begin{array}{lll} z(r)&=\beta(r) & \mbox{dla } r=0,1, \dots L-1\\ z(Ln+r)&=\alpha z(n) + \beta(r)& \mbox{dla } r=0,1\dots L-1; n>0\end{array} \right.

oraz załóżmy, że \beta jest permutacją zbioru \{0,1, \dots L-1\}. Wtedy  gdy \alpha \in \mathbb{N} oraz

  1.   \alpha=L, to z jest bijekcją,
  2. 1<\alpha<L, to z jest surjekcją, ale nie jest injekcją,
  3. L < \alpha, to z jest injekcją, ale nie jest surjekcją.

Uogólnimy teraz nasze równanie. Kolejnym krokiem będą różne współczynniki \alpha, w zależności od reszty z dzielenia.

Twierdzenie 2.

Weźmy L \in \mathbb{N}_2, dowolne liczby \alpha(r)\neq 0, \beta(r)  dla r=0,1, \dots L-1 oraz rozważmy równanie rekurencyjne.
\left\{ \begin{array}{lll} z(r)&=\beta(r) & \mbox{dla } r=0,1, \dots L-1\\ z(Ln+r)&=\alpha(r) z(n) + \beta(r)& \mbox{dla } r=0,1\dots L-1; n>0\end{array} \right.

Wtedy dla dowolnej liczby naturalnej \displaystyle n=\sum_{i=0}^Nc_i L^i przedstawionej w systemie pozycyjnym o podstawie L mamy wzór

\displaystyle z(c_N\dots c_1 c_0)=z\left(\sum_{i=0}^N c_iL^i\right)=\sum_{i=0}^N \beta(c_i)\prod_{j=0}^{i-1} \alpha(c_j)

przy czym, dla zwięzłości zapisu, przyjmujemy naturalną konwencję \displaystyle \prod_{j=0}^{-1} a_j=\prod_{j \in \emptyset} a_j=1.

Dowód.

Podobnie jak wcześniej oznaczmy przez \hat{z} kandydata na rozwiązanie z tezy, tzn.

\displaystyle \hat{z}(c_N\dots c_1 c_0)= \sum_{i=0}^N \beta(c_i) \prod_{j=0}^{i-1} \alpha(c_j).

Sprawdźmy zgodność warunków początkowych. Niech c_0=0,1,\dots L-1 wtedy

\displaystyle \hat{z}(c_0)=\beta(c_0) \prod_{j=0}^{-1} \alpha(c_j)=\beta(c_0)=z(c_0)

Sprawdzimy teraz jaka zależność rekurencyjna opisuje \hat{z}. Niech Ln+r=c_N\dots c_1 c_0. Wtedy r=c_0. Policzmy najpierw ile wynosi \hat{z}(Ln+r).

\displaystyle \hat{z}(Ln+r)=\hat{z}(c_N\dots c_1 c_0)=\sum_{i=0}^N \beta(c_i)\prod_{j=0}^{i-1} \alpha(c_j).

Wydzielamy teraz zerowy składnik sumy oraz zerowy składnik iloczynu i korzystamy z tego, że c_0=r

\displaystyle \sum_{i=1}^N \beta(c_i) \alpha(c_0)\prod_{j=1}^{i-1}\alpha(c_j) +\beta(c_0)=\alpha(r)\sum_{i=1}^N \beta(c_i) \prod_{j=1}^{i-1}\alpha(c_j)+\beta(r).

Widzimy, że wystarczy pokazać, że to, co jest przemnożone przez \alpha(r) jest \hat{z}(n). Mamy że

\displaystyle n=c_N\dots c_2 c_1=\sum_{i=1}^N L^{i-1}=\sum_{i=0}^{N-1} c_{i+1} L^i. Oznaczmy d_i:=c_{i+1}. Oznacza to równość n=d_{N-1}\dots d_1 d_0. Policzmy

\displaystyle \hat{z}(n)=\sum_{i=0}^{N-1} \beta( d_i ) \prod_{j=0} ^{i-1} \alpha (d_j)=\sum_{i=0}^{N-1} \beta( c_{i+1} ) \prod_{j=0} ^{i-1} \alpha (c_{j+1}).

Zamieniamy wskaźnik iloczynu następująco l=j+1, otrzymujemy

\displaystyle \hat{z}(n)=\sum_{i=0}^{N-1} \beta( c_{i+1} ) \prod_{l=1} ^{i} \alpha (c_l).

Następnie zamieniamy wskaźnik sumowania, analogicznie biorąc k=i+1. Wtedy, zmianie ulega, poza granicami sumowania również górna granica iloczynu. Ostatecznie otrzymaliśmy

\displaystyle \hat{z}(n)=\sum_{k=1}^{N} \beta( c_k ) \prod_{l=1} ^{k-1} \alpha (c_l)

co oznacza, że

\hat{z}(Ln+r)=\alpha(r) \hat{z}(n) +\beta(r).

Zatem \hat{z}(n)=z(n) dla wszystkich naturalnych n. qed

Widać przy okazji, że gdy w powyższym twierdzeniu przyjmiemy jedną i tę sama alfę dla wszystkich reszt otrzymamy poprzednie twierdzenie. Nadal nie pozbyliśmy się założenia o zgodności wyrazów początkowych z wyrazami wolnymi, ale wkrótce i to przeskoczymy. Najpierw jednak przykład rozwiązania.

Przykład 5.

Rozważmy tzw. ciąg Thue-Morse’a

\left\{ \begin{array}{ll} t(0)&=0 \\ t(2n)&=t(n) \\ t(2n+1)&=1-t(n) \\ \end{array} \right.

Wyznaczymy rozwiązanie tej rekurencji korzystając z Twierdzenia 2. Mamy z definicji t(1)=1-t(0)=1. Zatem używając oznaczeń z twierdzenia \beta(0)=0 i \beta(1)=1, co oznacza po prostu \beta(r)=r. Jeśli chodzi o współczynniki alfa to \alpha(0)=1 i \alpha(1)=-1, a więc możemy zapisać \alpha(r)=(-1)^r. Stosujemy twierdzenie, oczywiście przy L=2 i otrzymujemy dla n=c_N\dots c_1 c_0

\displaystyle t(n)=\sum_{i=0}^N c_i \prod_{j=0}^{i-1} (-1)^{c_j}=\sum_{i=0}^N c_i (-1)^{\displaystyle \sum_{j=0}^{i-1} c_j}.

Nie wygląda to dobrze, ale da się uprościć to wyrażenie. Niech 0<i_0<i_1 \dots <i_k=N będą indeksami wszystkich tych cyfr w rozwinięciu n, które są równe jeden, tylko one mają znaczenie w powyższej sumie. Możemy więc zapisać, że

\displaystyle t(n)=\sum_{l=0}^k c_{i_l} (-1)^{\displaystyle \sum_{j=0}^{l-1} c_{i_j}}=\sum_{l=0}^k (-1)^{\displaystyle \sum_{j=0}^{l-1} c_{i_j}}.

Przyjmy się teraz każdym dwóm kolejnym sumom występującym w potęgach minus jedynek. Zauważmy, że

\displaystyle \sum_{j=0}^{l-1}c_{i_j}+1=\sum_{j=0}^l c_{i_j}

oznacza to, że

\displaystyle (-1)^{\displaystyle \sum_{j=0}^{l-1}c_{i_j}}=-(-1)^{\displaystyle \sum_{j=0}^l c_{i_j}}.

Zatem gdy liczba składników całej sumy, będącej rozwiązaniem, jest parzysta to t(n)=0, ale zauważmy, że liczba składników to suma cyfr s_2(n). Rozważmy teraz przypadek, gdy s_2(n) jest nieparzysta. Wtedy z całej sumy zostaje nam, np. tylko ostatni składnik i korzystając z nieparzystości s_2(n) oraz faktu, że c_N=1 dostajemy

t(n)=(-1)^{\displaystyle \sum_{j=0}^{k-1} c_{i_j} }=(-1)^{\displaystyle s_2(n)-c_N}=(-1)^{\displaystyle s_2(n)-1}=1.

Ostatecznie możemy napisać

\displaystyle t(n)=\frac{(-1)^{\displaystyle s_2(n)-1}+1}{2}.

co zgadza się z powszechną wiedzą na temat tegoż ciągu.

 

Teraz będziemy chcieli się pozbyć założenia o zgodności wyrazów początkowych z wyrazami wolnymi.

Rozważmy równanie

z(Ln+r)=\alpha(r) z(n)+\beta(r) dla n>0 i r=0,1, \dots L-1

z dowolnymi wyrazami wolnymi z(0), z(1), \dots z(L-1).

Zastosujmy podstawienie

w(n):=z(Ln+r)-z(r)

dla każdego n. A priori nie wiadomo czy ma ono sens, ale spróbujmy wyliczyć zależność rekurencyjną, jaką spełnia w. Mamy po pierwsze, że dla r=0,1, \dots L-1

w(r)=z(Lr+r)-r=\alpha(r)z(r)+\beta(r)-z(r)=z(r)(\alpha(r)-1)+\beta(r)

Ponadto dla n>L-1

w(Ln+r)=z(L(Ln+r)+r)-z(r)=\alpha(r)z(Ln+r)+\beta(r)

=\alpha(r)(w(n)+z(r))+\beta(r)-z(r)=\alpha(r)w(n)+z(r)(\alpha(r)-1)+\beta(r)

Szybki rzut okiem pozwala stwierdzić, że dla ciągu w spełnione są założenia Twierdzenia 2. z tymi samymi współczynnikami \alpha(r) oraz z wyrazami początkowymi/wolnymi postaci z(r)(\alpha(r)-1)+\beta(r).Zatem gdy n=c_N\dots c_1c_0, to

\displaystyle w(n)=\sum_{i=0}^N (z(c_i)(\alpha(c_i)-1)+\beta(c_i)) \prod_{j=0}^{i-1}\alpha(c_j).

Jeśli chcemy policzyć wyjściowy ciąg wystarczy skorzystać z zależności z(nL+r)=w(n)+z(r).

Widać też, że w jest ciągów spełniających założenia Twierdzenia 2.Wszystkie tych samych współczynnikach \alpha(r), ale o różnych wyrazach wolnych równych odpowiednio z(r)\alpha(r), -z(r), \beta(r).

Przejdźmy jednak już do głównego twierdzenia, które i tak obejmuje wszystkie poprzednie przypadki. Mianowicie będziemy rozważać, jak to zapowiedziałem, współczynniki alfa i beta różne nie tylko dla różnych reszt, ale też zależne od n.

Twierdzenie 3.

Niech L \in \mathbb{N}_2 oraz dla r=0,1, \dots L-1 dane niech będą ciągi \{\alpha_n(r)\}_{n=1}^\infty, \{\beta_n(r)\}_{n=0}^\infty. Definiujemy rekurencyjnie ciąg

z(Ln+r):=\alpha_n(r)z(n)+\beta_n(r) dla n>0 i r=0,1,\dots L-1

oraz z(r):=\beta_0(r).

Wtedy gdy n=c_N\dots c_1 c_0 to

\displaystyle z(n)=\sum_{i=0}^N \beta_{\displaystyle c_{N+1}c_N\dots c_{i+1}}(c_i) \prod_{j=0}^{i-1} \alpha_{\displaystyle c_Nc_{N-1}\dots c_{j+1}}(c_j)

gdzie \displaystyle c_N c_{N-1} \dots c_{i}=\sum_{k=i}^Nc_kL^{k-i}.

Dowód.

Zauważmy najpierw, że

\displaystyle z(c_N\dots c_1 c_0)= z\left( L\sum_{i=1}^N c_i L^{i-1}+c_0\right)=z(L\cdot c_N c_{N-1}\dots c_1+ c_0)

=\alpha_{\displaystyle c_N c_{N-1}\dots c_1} (c_0) z( c_N c_{N-1}\dots c_1)+\beta_{\displaystyle c_Nc_{N-1}\dots c_1}(c_0)

Oznaczmy przez \hat{z} kandydata na rozwiązanie z tezy. Pokażemy że spełnia powyższą zależność rekurencyjną dla rozwinięć liczb oraz, że ma te same wyrazy początkowe, co z.

Zauważmy najpierw, że dla c_0=c mamy \hat{z}(c)=\beta_{c_1}(c_0)\cdot 1=\beta_0(c)=z(c).

Policzmy teraz zależność rekurencyjną

\displaystyle \hat{z}(c_N\cdots c_1 c_0)=

\displaystyle \alpha_{\displaystyle c_N c_{N-1}\dots c_1}(c_0)\sum_{i=1}^N \beta_{\displaystyle c_{N+1}c_N\dots c_{i+1}}(c_i) \prod_{j=1}^{i-1} \alpha_{\displaystyle c_Nc_{N-1}\dots c_{j+1}}(c_j)+\beta_{\displaystyle c_{N+1}c_N\dots c_1}(c_0)

Postąpimy tak samo jak w dowodzie poprzedniego twierdzenia. Oznaczmy d_i:=c_{i+1}. Wtedy mamy

\displaystyle \hat{z}(c_Nc_{N-1} \dots c_1)=\hat{z}(d_{N-1} \dots d_1 d_0)=\sum_{i=0}^{N-1} \beta_{\displaystyle d_{N}d_{N-1}\dots d_{i+1}}(d_i) \prod_{j=0}^{i-1} \alpha_{\displaystyle d_{N-1}\dots d_{j+1}}(d_j)

i dalej

\displaystyle =\sum_{i=0}^{N-1} \beta_{\displaystyle c_{N+1}c_N\dots c_{i+2}}(c_{i+1}) \prod_{j=0}^{i-1} \alpha_{\displaystyle c_N c_{N-1}\dots c_{j+2}}(c_{j+1}).

Dokonując zamiany wskaźnika iloczynu l:=j+1, dostajemy

\displaystyle =\sum_{i=0}^{N-1} \beta_{\displaystyle c_{N+1}c_N\dots c_{i+2}}(c_{i+1}) \prod_{l=1}^i \alpha_{\displaystyle c_N c_{N-1}\dots c_{l+1}}(c_{l}).

Zaś zamieniając wskaźnik sumowania k=i+1, otrzymujemy dalej

\displaystyle =\sum_{k=1}^N \beta_{\displaystyle c_{N+1}c_N\dots c_{k+1}}(c_{k}) \prod_{l=1}^{k-1} \alpha_{\displaystyle c_N c_{N-1}\dots c_{l+1}}(c_{l}).

Widać więc, że

\hat{z}(c_N\dots c_1 c_0)= \alpha_{\displaystyle c_N c_{N-1}\dots c_1} (c_0) \hat{z}( c_N c_{N-1}\dots c_1)+\beta_{\displaystyle c_Nc_{N-1}\dots c_1}(c_0).

Biorąc pod uwagę również zgodność między z a \hat{z} dla warunków początkowych oznacza to, że \hat{z}\equiv z. qed

Przykład 6.

Wyliczymy rozwiązanie rekurencji ciągu Rudina-Shapiro

\left\{ \begin{array}{ll} a_0&=1 \\ a_{2n}&=a_n \\ a_{2n+1}&=(-1)^n a_n\\ \end{array}\right.

Po pierwsze zauważmy, że \beta_0(r)=1 oraz \beta_n(r)=0 gdy n > 0 a także \alpha_n(r)=(-1)^{rn}. Zatem dla 0<n=\displaystyle \sum_{i=0}^N c_i 2^i mamy ogólnie

\displaystyle a(n)=\sum_{i=0}^N \beta_{\displaystyle c_{N+1}c_N\dots c_{i+1}}(c_i) \prod_{j=0}^{i-1} \alpha_{\displaystyle c_Nc_{N-1}\dots c_{j+1}}(c_j)

ale \beta_{\displaystyle c_{N+1}c_N\dots c_{i+1}}(c_i)=0 dla i<N, gdyż c_{N+1}c_N \dots c_{i+1}>0 dla i< N. Natomiast dla i=N mamy \beta_{C_{N+1}}(c_N)=\beta_0(1)=1. Zatem

\displaystyle a(n)=\prod_{j=0}^{N-1} \alpha_{\displaystyle c_Nc_{N-1}\dots c_{j+1}}(c_j).

Zauważmy jednak, że

(-1)^{\displaystyle c_Nc_{N-1}\dots c_{j+1}}=(-1)^{\displaystyle c_{j+1}}.

Zatem

\alpha_{\displaystyle c_Nc_{N-1}\dots c_{j+1}}(c_j)=(-1)^{\displaystyle c_j c_{j+1}}.

Czyli ostateczenie mamy wzór

\displaystyle a(n)=\prod_{j=0}^{N-1} (-1)^{\displaystyle c_j c_{j+1}}=(-1)^{\displaystyle \sum_{j=0}^{N-1} c_jc_{j+1}}

który zgadza się również dla n=0 oraz który zgadza się z powszechną wiedzą na temat tego ciągu.

Ogólnie przedstawione metody rozwiązywania tego typu równań są o tyle pozytywne, że dają, jakby nie było, jawne rozwiązanie. Jednak osobną sztuką jest uczynienie tego rozwiązania czytelnym, co widać po jego postaci ogólnej i po przykładach, szczególnie po niewinnie zapowiadającym się ciągu Thue-Morse’a. Kolejną zaletą jest to, że nie musimy mieć pomysłu jak rozwiązanie ma wyglądać. Po prostu wystarczy próbować je uprościć.

Reklamy