Równania rekurencyjne

[justynian]

Wstęp

Jak wiadomo za pomocą równań rekurencyjnych możemy definiować ciągi liczbowe. Niestety bywa tak że o zadanym w ten sposób ciągu chcemy wiedzieć jaką postać jawną ma konkretny jego wyraz a obliczanie jej za pomocą zadanej zależności rekurencyjnej bywa bardzo uciążliwe. Prezentowany tutaj zbiór metod rozwiązywania (znajdowania postaci jawnej ciągów) omawianych równań może być w wielu przypadkach bardzo pomocny. Zaznaczam jednak że prezentowane algorytmy mają charakter praktyczny i nie będziemy zajmować się dowodzeniem ich prawdziwości.

1. Liniowe równania rekurencyjne jednorodne o stałych współczynnikach rzędu k mają postać:

\(\displaystyle{ x_n=a_1x_{n-1}+a_2x_{n-2}+...+a_kx_{n-k} \ \ \ \ (1)}\)

gdzie: \(\displaystyle{ n>k, \ \forall _{i \in \left\{1,2,..,k\right\}=I_k} \ a_i \in \CC}\) są współczynnikami, a ciąg \(\displaystyle{ (x_i)_{i \in N_+}}\) jest przez \(\displaystyle{ (1)}\) i \(\displaystyle{ k}\) początkowych wyrazów zdefiniowany. Umawiamy się też stosować od teraz utożsamienie \(\displaystyle{ \forall_{k \in N_+} \left\{1,2,...,k\right\}=I_k}\).

Aby je rozwiązać należy zauważyć że ciąg zadany w sposób: \(\displaystyle{ x_n= x^n}\), spełnia nasze równanie wtedy i tylko wtedy gdy \(\displaystyle{ x}\) jest pierwiastkiem stowarzyszonego równania charakterystycznego równania \(\displaystyle{ (1)}\) postaci:

\(\displaystyle{ x^k-a_1x^{k-1}-a_2x^{k-2}-...-a_{k-1}x-a_k=0 \ \ \ \ (2)}\)

Na mocy zasadniczego twierdzenia algebry ma ono k pierwiastków, wielokrotnych lub nie. Jeżeli oznaczymy je przez \(\displaystyle{ \alpha_1, \ \alpha_2, \ ..., \ \alpha_l}\), \(\displaystyle{ l \le k}\), a ich krotności odpowiednio przez \(\displaystyle{ p_1, \ p_2, \ ..., \ p_l}\) gdzie oczywiście \(\displaystyle{ \forall_{i \in I_l}p_i \ge 1}\) oraz \(\displaystyle{ p_1 + p_2 + ... + p_l = k}\) to rozwiązanie \(\displaystyle{ (1)}\) ma postać:

\(\displaystyle{ x_n=\sum_{m=1}^{l}\left(\sum_{i=0}^{p_m-1}b^{(m)}_{i}n^i \right)\left(\alpha_m\right)^n \ \ \ \ (3)}\)

gdzie: \(\displaystyle{ \forall_{m \in I_l} \forall_{i \in \left\{0,1,...,p_m-1 \right\}} b^{(m)}_{i} \in \CC}\) są współczynnikami wyznaczanymi przez podstawienie wartości początkowych wyrazów do \(\displaystyle{ (3)}\). W szczególności jeśli \(\displaystyle{ l=k}\) tzn. jeśli wszystkie pierwiastki są pojedynczej krotności otrzymamy:

\(\displaystyle{ x_n=\sum^{k}_{m=1}b_m(\alpha_m)^n \ \ \ \ (4)}\)

gdzie: \(\displaystyle{ \forall_{m \in I_k}b_m \in \CC}\) i tym razem to one grają rolę współczynników.

Przykład 1.

\(\displaystyle{ x_n=2x_{n-1}, \ x_1=2, \ n>1}\)

Rozwiązanie:    

Równanie charakterystyczne ma postać:

\(\displaystyle{ x-2=0}\)

którego rozwiązaniem jest \(\displaystyle{ \alpha_1=2}\). Rozwiązanie ogóle ma zatem postać:

\(\displaystyle{ x_n=A(2)^n.}\)

Obliczając z niego wartość dla \(\displaystyle{ x_1}\) mamy:

\(\displaystyle{ x_1=2A \mathop{=}_{ \substack{\text{z warunku} \\ \text{początkowego}} }2}\)

a zatem \(\displaystyle{ A=1}\) i ostatecznie nasz ciąg zadany jest w sposób jawny: \(\displaystyle{ x_n=2^n.}\)

Przykład 2.

\(\displaystyle{ F_n=F_{n-1}+F_{n-2}, \ F_1=1, \ F_2=1, \ n>2}\)

Rozwiązanie:    

Równanie charakterystyczne ma postać:

\(\displaystyle{ x^2-x-1=0}\)

którego rozwiązaniami są \(\displaystyle{ \alpha_1= \frac{1+\sqrt{5}}{2}, \ \alpha_2= \frac{1-\sqrt{5}}{2}}\). Rozwiązanie ogóle ma zatem postać:

\(\displaystyle{ F_n=A\left(\frac{1+\sqrt{5}}{2}\right)^n+B\left(\frac{1-\sqrt{5}}{2}\right)^n.}\)

Obliczając z niego wartość dla \(\displaystyle{ F_1, \ F_2}\) mamy:

\(\displaystyle{ \begin{cases}F_1=A\left(\frac{1+\sqrt{5}}{2}\right)+B\left(\frac{1-\sqrt{5}}{2}\right)=1 \\
F_2=A\left(\frac{1+\sqrt{5}}{2}\right)^2+B\left(\frac{1-\sqrt{5}}{2}\right)^2=1 \end{cases}}\)

rozwiązując ten układ otrzymamy \(\displaystyle{ A=\frac{1}{\sqrt{5}}, \ B=-\frac{1}{\sqrt{5}}}\) i ostatecznie nasz ciąg zadany jest w sposób jawny: \(\displaystyle{ F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2} \right)^n.}\) Warto dodać że rozważany ciąg nazywany jest ciągiem Fibonacciego, a jego postać jawna wzorem Bineta.

Przykład 3.

\(\displaystyle{ x_n=x_{n-1}-ix_{n-2}+ix_{n-3}, \ x_1=1, \ x_2=1-2i, \ x_3=1, \ n>3}\)

Rozwiązanie:    

Równanie charakterystyczne ma postać:

\(\displaystyle{ x^3-x^2+ix-i=0 \\ x^2(x-1)+i(x-1)=0 \\ (x-1)(x^2+i)=0}\)

którego rozwiązaniami są \(\displaystyle{ \alpha_1=1, \ \alpha_2=\sqrt{-i}, \ \alpha_3=-\sqrt{-i}}\). Rozwiązanie ogóle ma zatem postać:

\(\displaystyle{ x_n=A(1)^n+B(\sqrt{-i})^n+C(-\sqrt{-i})^n.}\)

Obliczając z niego wartości dla \(\displaystyle{ x_1, \ x_2, \ x_3}\) mamy:

\(\displaystyle{ \begin{cases}x_1=A+B\sqrt{-i}-C\sqrt{-i}=1 \\
x_2=A-Bi-Ci = 1-2i \\
x_3=A-B\sqrt{-i}+C\sqrt{-i}=1 \end{cases}}\)

rozwiązując ten układ otrzymamy: \(\displaystyle{ A=B=C=1}\) ostatecznie nasz ciąg zadany jest w sposób jawny: \(\displaystyle{ x_n=1+(\sqrt{-i})^n+(-\sqrt{-i})^n.}\)

2.Liniowe równania rekurencyjne jednorodne o zmiennych współczynnikach rzędu k są postaci:

\(\displaystyle{ x_n=a^{(1)}_nx_{n-1}+a^{(2)}_nx_{n-2}+...+a^{(k)}_{n}x_{n-k}}\)

gdzie: \(\displaystyle{ n>k, \ ( a^{(1)}_n)^{\infty}_{n=k+1}, \ ( a^{(2)}_n)^{\infty}_{n=k+1}, \ ..., \ ( a^{(k)}_n)^{\infty}_{n=k+1}}\) są zadanymi ciągami współczynników takich że \(\displaystyle{ \forall_{ i \in I_k} \forall_{n \in \left\{k+1,k+2,...\right\}}a^{(i)}_n \in \CC}\). Nie będziemy jednak zajmować się wszystkimi równaniami tego typu a jedynie szczególnym przypadkiem rzędu pierwszego tzn. iloczynem nieskończonym postaci:

\(\displaystyle{ x_n=a_nx_{n-1} \ \ \ \ (5)}\)

postać jawna tego ciągu to:

\(\displaystyle{ x_n=x_1\prod^{n}_{i=2}a_1 \ \ \ \ (6)}\)

Przykład 1.

\(\displaystyle{ x_n=nx_{n-1}, \ x_1=1, \ n>1}\)

Rozwiązanie:    

W naszym przypadku mamy \(\displaystyle{ a_i=i, \ i>1}\) zatem zgodnie z \(\displaystyle{ (6)}\) \(\displaystyle{ x_n= 1\cdot \prod^{n}_{i=2}i=n!}\)

Przykład 2.

\(\displaystyle{ x_n=\frac{n-1}{n}x_{n-1}, \ x_1=1, \ n>1}\)

Rozwiązanie:    

Widzimy że \(\displaystyle{ a_n=\frac{n-1}{n}}\) więc rozwiązanie ma postać: \(\displaystyle{ x_n=1\cdot \prod^{n}_{i=2}\frac{i-1}{i}=\frac{1}{2} \cdot \frac{2}{3} \cdot ... \cdot \frac{n-1}{n}=\frac{1}{n}}\)

Przykład 3.

\(\displaystyle{ x_n=\frac{5^n}{n}x_{n-1}, \ x_1=5, \ n>1}\)

Rozwiązanie:    

Tym razem \(\displaystyle{ a_n=\frac{5^n}{n}}\) więc z \(\displaystyle{ (6)}\): \(\displaystyle{ x_n=5 \cdot \prod^{n}_{i=2}\frac{5^i}{i}=\frac{5^{\frac{n(n+1)}{2}}}{n!}}\)

3. Liniowym równaniem rekurencyjnym niejednorodnym o stałych współczynnikach rzędu k nazywamy równanie postaci:

\(\displaystyle{ x_n=a_1x_{n-1}+a_2x_{n-2}+...+a_kx_{n-k}+f(n) \ \ \ \ (7)}\)

gdzie: \(\displaystyle{ n>k, \ \forall_{i \in I_k}a_i \in \CC}\) są współczynnikami, a \(\displaystyle{ f(n)}\) oznacza funkcję zmiennej n taką że \(\displaystyle{ f(n)\not\equiv 0.}\)

Rozwiązując równanie \(\displaystyle{ (7)}\) zajmujemy się najpierw równaniem powstałym przez odrzucenie z \(\displaystyle{ (7)}\) wyrazu \(\displaystyle{ f(n)}\) tzn. znalezieniem rozwiązania \(\displaystyle{ x^{(1)}_n}\) równania postaci \(\displaystyle{ (1)}\). Następnie poszukujemy tzw. szczególnego rozwiązania \(\displaystyle{ x^{(2)}_n}\) równania \(\displaystyle{ (7).}\) Rozwiązanie ogólne tego równania jest wtedy postaci:

\(\displaystyle{ x_n=x^{(1)}_n+x^{(2)}_n \ \ \ \ (8).}\)

Niestety znalezienie rozwiązania szczególnego nie jest zwykle zadaniem prostym, toteż użyteczna jest tzw. metoda przewidywań która dla niektórych postaci \(\displaystyle{ f(n)}\) mówi nam jaką postać man rozwiązanie szczególne. Oto te przypadki:

\(\displaystyle{ \star}\) Jeżeli \(\displaystyle{ f(n)=a \neq 0 \ \wedge \ \sum_{i=1}^k a_i \neq 1}\) to \(\displaystyle{ x^{(2)}_n=\frac{a}{1- \sum_{i=1}^k a_i}}\)

\(\displaystyle{ \star}\) Jeżeli \(\displaystyle{ f(n)=a\neq 0 \ \wedge \ \sum_{i=1}^k a_i = 1}\) to \(\displaystyle{ x^{(2)}_n=n\frac{a}{\sum_{i=1}^k ia_i}}\)

\(\displaystyle{ \star}\) Jeżeli \(\displaystyle{ f(n)=A\alpha^n}\) i \(\displaystyle{ \alpha}\) nie jest pierwiastkiem równania charakterystycznego
równania \(\displaystyle{ (1)}\) stowarzyszonego z równaniem \(\displaystyle{ (7)}\) to \(\displaystyle{ x^{(2)}_n=B\alpha^n}\)

\(\displaystyle{ \star}\) Jeżeli \(\displaystyle{ f(n)=A\alpha^n}\) i \(\displaystyle{ \alpha}\) jest pierwiastkiem \(\displaystyle{ k \ge 1}\) krotnym równania charakterystycznego
równania \(\displaystyle{ (1)}\) stowarzyszonego z równaniem \(\displaystyle{ (7)}\) to \(\displaystyle{ x^{(2)}_n=Bn^k\alpha^n}\)

\(\displaystyle{ \star}\)Jeżeli \(\displaystyle{ f(n)=w_d(n)}\) (gdzie \(\displaystyle{ w_d(n)}\) oznacza wielomian stopnia d zmiennej n) a \(\displaystyle{ x^{(1)}_n}\) nie jest wielomianem zmiennej n to \(\displaystyle{ x^{(2)}_n=q_{max \ d}(n)}\) (gdzie \(\displaystyle{ q_{max \ d}(n)}\) oznacza wielomian stopnia co najwyżej d zmiennej n)

\(\displaystyle{ \star}\)Jeżeli \(\displaystyle{ f(n)=w_d(n)}\) a \(\displaystyle{ x^{(1)}_n}\) jest wielomianem stopnia \(\displaystyle{ k}\) zmiennej n to \(\displaystyle{ x^{(2)}_n=n^{k+1}q_{max \ d}(n)}\)

Jeżeli natomiast \(\displaystyle{ f(n)}\) jest sumą/różnicą wspomnianych klas funkcji to rozwiązanie szczególne jest sumą/różnicą przewidywanych rozwiązań szczególnych. Warto także zatrzymać się na równaniu niejednorodnym:

\(\displaystyle{ x_n=x_{n-1}+f(n) \ \ \ \ (9)}\)

nazywanym sumą nieskończoną (jest to po prostu suma częściowa pewnego szeregu). Mamy tutaj łatwy do wyznaczenia wzór jawny:

\(\displaystyle{ x_n=x_1 + \sum^{n}_{i=2}f(i) \ \ \ \ (10).}\)

O ile jednak otrzymanie takiej postaci jest łatwe to jej przekształcenie na postać zwartą już nie zawsze takie jest. Zależy to oczywiście od postaci \(\displaystyle{ f(n)}\), i jest raczej zagadnieniem bardziej charakterystycznym przy rozważaniu szeregów, godny wspomnienia tutaj przypadek ma miejsce gdy: \(\displaystyle{ f(n)=n^{\underline{m}}\alpha^{n-m}}\) gdzie \(\displaystyle{ x^{\underline{m}}=n(n-1)...(n-m+1)}\) to tzw. potęga ubywająca, można bowiem skorzystać wtedy z tożsamości: \(\displaystyle{ (\alpha^n)^{(m)}=n^{\underline{m}}\alpha^{n-m}.}\)

Przykład 1.

\(\displaystyle{ x_n=2x_{n-1}+1, \ x_1=1, \ n>1}\)

Rozwiązanie:    

Rozważamy równanie jednorodne \(\displaystyle{ x-2=0}\) zatem \(\displaystyle{ \alpha_1=2}\) toteż:

\(\displaystyle{ x^{(1)}_n=A2^n.}\)

\(\displaystyle{ f(n)=1}\) i suma współczynników po prawej stronie naszej rekurencji jest różna od jedności więc przewidujemy że:

\(\displaystyle{ x^{(2)}_n=-1.}\)

Zgodnie z wzorem \(\displaystyle{ (8),}\) \(\displaystyle{ x_n = A2^n-1}\). Obliczając teraz \(\displaystyle{ x_1=2A-1=1 \ \Leftrightarrow \ A=1}\) mamy że nasze rozwiązanie przyjmuje postać: \(\displaystyle{ x_n = 2^n-1.}\)

Przykład 2.

\(\displaystyle{ x_n=x_{n-1}+\frac{1}{n(n-1)}, \ x_1=0, \ n>1}\)

Rozwiązanie:    

Tutaj \(\displaystyle{ f(n)=\frac{1}{n(n-1)}}\) Stosując \(\displaystyle{ (10)}\) otrzymamy: \(\displaystyle{ x_n=0+\sum^n_{i=2}\frac{1}{i(i-1)}=\frac{1}{1}-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+...+\frac{1}{(n-1)}-\frac{1}{n}=1-\frac{1}{n}.}\)

Przykład 3.

\(\displaystyle{ x_n=-6x_{n-1}-9x_{x-2}+3^n, \ x_1=-3, \ x_2=36, \ n>2}\)

Rozwiązanie:    

Równanie jednorodne ma postać: \(\displaystyle{ x^2+6x+9=0 \ \Leftrightarrow \ (x+3)=0}\) którego pierwiastkiem dwukrotnym jest \(\displaystyle{ \alpha_1=-3.}\) Otrzymujemy:

\(\displaystyle{ x^{(1)}_n=A(-3)^n+Bn(-3)^n.}\)

\(\displaystyle{ f(n)=3^n}\) przewidujemy więc rozwiązanie szczególne \(\displaystyle{ x^{(2)}_n=C3^n.}\) W celu wyznaczenia C wstawiamy rozwiązanie \(\displaystyle{ x^{(2)}_n}\) bezpośrednio do naszego równania rekurencyjnego, otrzymujemy: \(\displaystyle{ C3^n=-6C3^{n-1}-9C3^{n-2}+3^n \ \Leftrightarrow \ 4C3^n=3^n}\) więc \(\displaystyle{ C=\frac{1}{4}}\). Rozwiązanie ogólne na mocy \(\displaystyle{ (8)}\) i tego cośmy obliczyli ma postać: \(\displaystyle{ x_n=A(-3)^n+Bn(-3)^n+\frac{1}{4}3^n.}\). Obliczając z niego \(\displaystyle{ x_1 \ i \ x_2}\) dostaniemy:

\(\displaystyle{ \begin{cases} x_1=-3A-3B+\frac{3}{4}=-3 \\ x_2=9A+18B+\frac{9}{4}=36 \end{cases}}\)

Rozwiązaniami są, co łatwo obliczyć: \(\displaystyle{ A=-\frac{5}{4}, \ B=\frac{5}{2}}\) a nasze rozwiązanie przybiera postać: \(\displaystyle{ x_n= -\frac{5}{4}(-3)^n+\frac{5}{2}n(-3)^n+\frac{1}{4}3^n.}\)

Przykład 4.

\(\displaystyle{ x_n=2ix_{n-1}+x_{n-2}+2n, \ x_1=1, \ x_2=i, \ n>2}\)

Rozwiązanie:    

Rozwiązując równanie \(\displaystyle{ x^2-2ix-1=0 \ \Leftrightarrow \ (x-i)=0}\) otrzymamy: \(\displaystyle{ \alpha_1=i}\) zatem \(\displaystyle{ x_n^{(1)}=Ai^n+Bni^n.}\) Rozwiązaniem szczególnym jest jako że \(\displaystyle{ f(n)=2n, \ x_n^{(2)}=Cn+D}\). Wyznaczamy współczynniki \(\displaystyle{ C,D}\) podobnie jak poprzednio: \(\displaystyle{ Cn+D=2iC(n-1)+2iD+C(n-2)+d+2n = (2iC+C+2)n+(2iD+D-2iC-2C) \Leftrightarrow}\)

\(\displaystyle{ \begin{cases} C=2iC+C+2 \\ D=D+2iD-2iC-2C \end{cases}}\)

rozwiązaniami są: \(\displaystyle{ C=i, \ D=1+i,}\) więc \(\displaystyle{ x_n^{(2)}=in+1+i}\) a \(\displaystyle{ x_n=Ai^n+Bni^n+in+1+i.}\) Wyliczamy \(\displaystyle{ x_1, \ x_2}\) otrzymując:

\(\displaystyle{ \begin{cases} x_1=Ai+Bi+2i+1=1 \\ x_2=-A-2B+3i+1=i \end{cases}}\)

rozwiązując ten układ otrzymamy: \(\displaystyle{ A=-2i-5, \ B=2i+3.}\) Rozwiązaniem ogólnym rekurencji jest więc \(\displaystyle{ x_n=-(2i+5)i^n+(2i+3)ni^n+in+1+i.}\)

4. Nieliniowe równania rekurencyjne są dużo bardziej różnorodne toteż bardzo trudno wskazać uniwersalne metody ich rozwiązywania. Zajmiemy się jednak analizą wybranych równań tego typu.

\(\displaystyle{ (a) \ \ \ \ x_n=\alpha x_{n-1}^{\beta}}\)

gdzie: \(\displaystyle{ \alpha,\beta >0, \ x_1>0, \ n>1}\). Równanie to sprowadza się przez obustronne zlogarytmowanie i podstawienie \(\displaystyle{ z_n=\ln x_n}\) do liniowego:

\(\displaystyle{ (a') \ \ \ \ z_n= \beta z_{n-1}+ \ln \alpha.}\)

\(\displaystyle{ (b) \ \ \ \ \alpha x_nx_{n+1}+\beta x_{n+1}+ \gamma=0}\)

gdzie: \(\displaystyle{ n \ge 1, \ \alpha, \ \beta, \ \gamma \in \CC,}\) równanie to także sprowadza się do liniowego tym razem podstawieniem \(\displaystyle{ x_n=\frac{z_n}{z_{n+1}}}\) przy założeniu że \(\displaystyle{ \forall_{n \in N_+}z_n \neq 0.}\) Otrzymamy:

\(\displaystyle{ (b') \ \ \ \ \alpha z_n+ \beta z_{n+1}+ \gamma z_{n+2}=0.}\)

Przy pomocy tego równania w prosty sposób otrzymujemy zwartą postać n-tego reduktu ułamka łańcuchowego \(\displaystyle{ [0; \ a, \ a, \ ... ]}\) gdyż redukt ten zadany jest równaniem:

\(\displaystyle{ x_n=\frac{1}{a+x_{n-1}}, \ x_1=0, \ a \in N_+, \ n>1.}\)

\(\displaystyle{ (c) \ \ \ \ x_n^l=a_1x_{n-1}^l+a_2x_{n-2}^l+...+a_kx_{n-k} + f(n)}\)

gdzie: \(\displaystyle{ n>k, l \in N_+ \ \forall_{i \in I_k}a_i \in \CC}\) a \(\displaystyle{ f(n)}\) jest funkcją zmiennej n. Stosuje się tutaj podstawienie \(\displaystyle{ x_n^k=z_n}\) (jest ono uprawomocnione o ile: \(\displaystyle{ \forall_{n \in N_+}x_n \ge 0}\) albo \(\displaystyle{ k}\) jest nieparzyste) aby otrzymać:

\(\displaystyle{ (c') \ \ \ \ z_n=a_1z_{n-1}+a_2z_{n-2}+...+a_kz_{n-k}+f(n).}\)

\(\displaystyle{ (d) \ \ \ \ x_n^{l_n}=\alpha x_{n-1}^{l_{n-1}}x_{n-2}^{l_{n-2}}...x_{n-k}^{l_{n-k}}}\)

gdzie: \(\displaystyle{ n>k, \ \alpha >0, \ \forall_{i \in \left\{0,1,...,k \right\}}l_{n-i} \in R_+, \ \forall_{n \in N_+}x_n>0.}\) Na podstawie \(\displaystyle{ (a)}\) można się domyślić że należy tutaj obustronnie zlogarytmować i zastosować podstawienie \(\displaystyle{ z_n=\ln x_n}\) aby otrzymać:

\(\displaystyle{ (d') \ \ \ \ l_nz_n=l_{n-1}z_{n-1}+l_{n-2}z_{n-2}+...+l_{n-k}z_{n-k} + \ln \alpha.}\)