Informatyka MIMUW

Przykład

Rozważmy ciąg Fibonacci'ego, tzn. ciąg $(f_0,f_1,f_2,f_3,\ldots)$ zdefiniowany w następujący sposób:

$\begin{align*} f_0 & =0, \\ f_1 & =1, \\ f_n & =f_{n-1}+f_{n-2}\quad\textrm{dla}\ n\geq 2. \end{align*}$

Znamy już postać zwartą jego wyrazów. Tym razem zobaczymy jak można ją otrzymać używając funkcji tworzących. Zależności rekurencyjne dla $f_n$ przekładają się natychmiast na następujące równanie, jakie musi spełniać funkcja tworząca ${F}(x)$ dla ciągu Fibonacci'ego

$\displaystyle {F}(x) =\sum_{n=0}^{\infty}f_nx^n =x+\sum_{n=2}^{\infty}(f_{n-1}+f_{n-2})x^n=x+x{F}(x)+x^2{F}(x).$

Przekształcając powyższe równanie otrzymujemy:

${F}(x)=\frac{x}{1-x-x^2}.$      (11)

Celem, który chcemy osiągnąć to wykorzystanie funkcji $\frac{x}{1-x-x^2}$ do przedstawienia współczynników $f_n$ w postaci zwartej. Pierwszym krokiem będzie rozłożenie ułamka w równaniu (11) na sumę ułamków o mianownikach będących funkcjami liniowymi

${F}(x)=\frac{x}{1-x-x^2} =\frac{x}{(1-z_0 x)(1-z_1 x)} =\frac{1}{\sqrt{5}}(\frac{1}{(1-z_0 x)}-\frac{1}{(1-z_1 x)}),$

gdzie $z_0=\frac{1+\sqrt{5}}{2}$ jest złotą liczbą oraz $z_1=\frac{1-\sqrt{5}}{2}$ liczbą do niej sprzężoną. Korzystając z równania (7) otrzymujemy teraz

$\displaystyle {F}(x) =\frac{1}{\sqrt{5}}(\sum_{n=0}^{\infty}{{z_0}^nx^n}-\sum_{n=0}^{\infty}{{z_1}^nx^n}) =\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}{({z_0}^n-{z_1}^n)x^n}.$

Tak więc dostajemy szybko znaną nam już postać zwartą $f_n=\frac{1}{\sqrt{5}}({z_0}^n-{z_1}^n)$.

Podczas rozwiązywania przykładu związanego z liczbami Fibonacci'ego natrafiliśmy na problem polegający na przedstawieniu w postaci szeregu wyrażenia $\frac{x}{1-x-x^2}$. Przyjrzymy się dokładniej tego typu wyrażeniom.

Stopień wielomianu $deg{{P}(x)}=n$, jeśli ${P}(x)=p_0+p_1x+\ldots+p_nx^n$.

Funkcja wymierna ${R}(x)$ to funkcja postaci $\frac{{P}(x)}{{Q}(x)}$, gdzie ${P}(x)$ oraz ${Q}(x)\neq0$ są wielomianami skończonego stopnia.

Obserwacja 7.6

Niech $A(x)$ oraz ${B}(x)$ będą wielomianami $deg{{A}(x)}\geq deg{{B}(x)}$. Wtedy istnieją wielomiany ${Q}(x)$ oraz ${R}(x)$ takie, że

${A}(x)={Q}(x){B}(x)+{R}(x),$

gdzie $deg{{R}(x)} < deg{{A}(x)}=deg{{Q}(x)}+deg{{B}(x)}$.

Przykład

Niech

${A}(x)=3x^5+5x^4+2x^3+x^2+2\quad\textrm{oraz}\quad{B}(x)=x^3+2x^2-1.$

Wtedy wielomiany

${Q}(x)=3x^2-x+3\quad\textrm{oraz}\quad{R}(x)=x+2$

spełniają

$\begin{align*}{A}(x) & =3x^5+5x^4+2x^3+x^2+2 \\ & =(3x^2-x+3)\cdot(x^3+2x^2-1)+x+2 \\ & ={Q}(x){B}(x)+{R}(x). \end{align*}$

Ponadto $deg{{A}(x)}=5=2+3=deg{{Q}(x)}+deg{{B}(x)}$.

Wniosek 7.7

Niech ${P}(x)$ oraz ${Q}(x)$ będą wielomianami takimi, że $deg{{P}(x)}\geq deg{{Q}(x)}$. Wtedy funkcję wymierną ${R}(x)={P}(x)/ {Q}(x),$ można przedstawić w postaci

${R}(x)=\frac{{P}(x)}{{Q}(x)}={A}(x)+\frac{{B}(x)}{{Q}(x)},$

dla pewnych wielomianów ${A}(x)$ oraz ${B}(x)$

spełniających $deg{{B}(x)} < deg{{Q}(x)}$.

Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi ${R}(x)={P}(x)/{Q}(x),$ dla których $deg{{P}(x)} < deg{{Q}(x)}$.

Twierdzenie 7.8

Niech ${P}(x)$ oraz ${Q}(x)$ będą wielomianami takimi, że

• $deg{{P}(x)} < deg{{Q}(x)}$,

• ${Q}(x)={S}(x){T}(x)$, gdzie oba wielomiany ${S}(x),{T}(x)$ są stopnia co najmniej $2$,

• $q_0\neq0$.

Wtedy istnieją wielomiany ${A}(x)$ oraz ${B}(x)$ takie, że $deg{{A}(x)} < deg{{S}(x)}$ i $deg{{B}(x)} < deg{{T}(x)}$ oraz

$\frac{{P}(x)}{{Q}(x)} =\frac{{A}(x)}{{S}(x)}+\frac{{B}(x)}{{T}(x)}.$

Uwaga

Twierdzenie 7.8 pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych.

Wniosek [Metoda rozwijania funkcji wymiernej w szereg] Rozważmy funkcję wymierną w postaci

${R}(x)=\frac{{P}(x)}{{Q}(x)},$

gdzie $deg{{P}(x)} < deg{{Q}(x)}$, oraz $q_0\neq0$. Załóżmy ponadto, że wielomian ${Q}(x)$ rozkłada się na następujący iloczyn czynników liniowych

${Q}(x) =q_0(1-\rho_1x)^{m_1}\cdot(1-\rho_2x)^{m_2}\cdot\ldots\cdot(1-\rho_kx)^{m_k}.$

Warto wspomnieć, że dalecy nie każdy wielomian ma taki rozkład. Na przykład $1+x^2$ jest nierozkładalny i nieliniowy. Wykorzystując parokrotnie Twierdzenie 7.8 otrzymujemy wielomiany ${P_1}(x),\ldots,{P_k}(x)$ takie, że

${R}(x) =\frac{{P}(x)}{{Q}(x)}=\frac{{P_1}(x)}{(1-\rho_1x)^{m_1}}+\frac{{P_2}(x)}{(1-\rho_2x)^{m_2}}+\ldots+\frac{{P_k}(x)}{(1-\rho_kx)^{m_k}},$

gdzie $deg{{P_i}(x)} < m_i$. Na mocy Obserwacji 7.6 możemy sprowadzić wielomian ${P_i}(x)$ do

$\begin{align*}{P_i}(x) & ={P_i^1}(x)(1-\rho_ix)+\gamma_{m_i} \\ & ={P_i^2}(x)(1-\rho_ix)^2+\gamma_{m_i-1}(1-\rho_ix)+\gamma_{m_i} \\ & \vdots \\ & =\gamma_1(1-\rho_ix)^{m_i-1}+\ldots+\gamma_{m_i-1}(1-\rho_ix)+\gamma_{m_i}, \end{align*}$

gdzie $m_i\geq deg{{P_i}(x)}>deg{{P_i^1}(x)}>deg{{P_i^2}(x)}>\ldots$. W konsekwencji otrzymamy

$\displaystyle {R}(x)\ =\ \sum_{i=1}^k{(\frac{\gamma_{i,1}}{1-\rho_ix}+\frac{\gamma_{i,2}}{(1-\rho_ix)^2}+\ldots+\frac{\gamma_{i,m_i}}{(1-\rho_ix)^{m_i}})}.$

Mnożąc teraz obie strony przez

${Q}(x)/q_0=(1-\rho_1x)^{m_1}\cdot(1-\rho_2x)^{m_2}\cdot\ldots\cdot(1-\rho_kx)^{m_k}$

i porównując współczynniki przy odpowiadających potęgach $x^i$ uzyskujemy pewien układ równań, rozwiązanie którego da nam poszukiwane współczynniki $\gamma_{i,j}$. Z drugiej strony, z Wniosku 7.5 wynika, że

$\displaystyle \frac{1}{(1-\rho x)^{m+1}} =\sum_{n=1}^{\infty}{ { m+n \choose m } \rho^n x^n}$

i w konsekwencji:

$\displaystyle [x^n]{R}(x)\ =\ \sum_{i=1}^k{\left(\gamma_{i,1}+ \gamma_{i,2}{n+1\choose 1}+ \ldots+ \gamma_{i,m_i}{n+m_i-1\choose m_i - 1}\right) }\rho_i^n.$      (12)

Przykład

Opisaną wyżej metodę ogólną zilustrujemy na przykładzie funkcji

${R}(x)=\frac{x^2}{1-x-x^2+x^3}.$

Wielomian $1-x-x^2+x^3$ ma jeden podwójny pierwiastek $x=1$ oraz jeden pojedynczy $x=-1$. Poznana metoda rozwijania funkcji wymiernej w szereg daje więc

${R}(x) =\frac{x^2}{(1-x)^2\cdot(1+x)}=\frac{\alpha}{1-x}+\frac{\beta}{(1-x)^2}+\frac{\gamma}{1+x}.$

Mnożąc obie strony przez $(1-x)^2\cdot(1+x)$ otrzymujemy:

$x^2=\alpha(1-x^2)+\beta(1+x)+\gamma(1-2x+x^2).$

Dwa wielomiany są równe, gdy współczynniki przy odpowiadających potęgach są sobie równe. Wartości $\alpha, \beta, \gamma$ można więc wyliczyć z układu równań

$\left \{ \begin{array} {l} \alpha & +\ \beta & +\ \gamma & = & 0 \\ \alpha & & -\ 2\gamma & = & 0 \\ & -\ \beta & +\ \gamma & = & 1. \end{array} \right.$

Rozwiązaniem powyższego układu są wartości $\alpha=-\frac{1}{4},\ \beta=\frac{1}{2},\ \gamma=-\frac{1}{4}.$ W konsekwencji otrzymujemy szereg

$\begin{align*}{R}(x) & =\sum_{n=0}^{\infty}(-\frac{1}{4}+\frac{1}{2}(n+1) - \frac{1}{4}(-1)^n)x^n \\ & =x^2+x^3+2x^4+2x^5+3x^6+3x^7+4x^8+\ldots. \end{align*}$

Jeżeli mianownik ${Q}(x)$ funkcji wymiernej ${R}(x)=\frac{{P}(x)}{{Q}(x)}$ posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład ${R}(x)$ na sumę.

Twierdzenie 7.9

Jeśli ${R}(x)={P}(x)/{Q}(x)$, gdzie ${Q}(x)=q_0\cdot(1-\rho_1x)\cdot\ldots\cdot(1-\rho_1x)$ i liczby $\rho_1,\ldots,\rho_l$ są parami różne, to w przypadku gdy ${P}(x)$ jest wielomianem stopnia mniejszego niż $l$, zachodzi

${x^n}{R}(x) =a_1\rho_1^n+\ldots+a_l\rho_l^n, \quad\textrm{dla}\ a_k=\frac{-\rho_k\cdot{P}(1/\rho_k)}{{Q'}(1/\rho_k)}.$

Przykład

Mianownik ${Q}(x)$ funkcji wymiernej

${R}(x)=\frac{{P}(x)}{{Q}(x)}=\frac{2x}{1-5x-2x^2+24x^3}.$

ma trzy różne pierwiastki i można ${R}(x)$ przedstawić jako

${R}(x)=\frac{2x}{(1+2x)(1-3x)(1-4x)}.$

Na mocy Twierdzenia 7.9 otrzymujemy więc, że

${x^n}{R}(x)=-\frac{2}{15}(-2)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.$

Jak widzieliśmy na przykładzie ciągu Fibonacci'ego, funkcje tworzące mogą być bardzo pomocne przy szukaniu postaci zwartej pewnych ciągów zadanych rekurencyjnie.

Jednorodne, liniowe równanie rekurencyjneto równanie postaci

$\left \{ \begin{array} {l} r_0 & = & c_0, \\ & \cdots & \\ r_{k-1} & = & c_{k-1}, \\ r_n & = & a_1r_{n-1}+a_2r_{n-2}+\ldots+a_kr_{n-k}\quad\textrm{dla}\ n\geq k, \end{array} \right .$

gdzie $c_0,\ldots,c_{k-1},a_1,\ldots,a_k$ są liczbami rzeczywistymi (niezależnymi od parametru rekurencyjnego $n$).

Rozważmy najpierw przypadek, gdy $k=2$, tzn. równanie postaci

$\left \{ \begin{array} {l} r_0 & = & c_0, \\ r_1 & = & c_1, \\ r_n & = & a_1r_{n-1}+a_2r_{n-2}\quad\textrm{dla}\ n\geq 2. \end{array} \right .$      (13)

Przykładem takiego równania była zależność opisująca ciąg Fibonacci'ego. Zastosowanie ostatniej równości z (13) do funkcji tworzącej ciągu $(r_0,r_1,r_2,\ldots)$ daje:

$\begin{align*}{R}(x) & =r_0+r_1x+r_2x^2+r_3x^3+\ldots+r_nx^n+\ldots \\ & =c_0+c_1x+(a_1r_1+a_2r_0)x^2+\ldots+(a_1r_{n-1}+a_2r_{n-2})x^n+\ldots \\ & =c_0+(c_1-a_1c_0)x+a_1x{R}(x)+a_2x^2{R}(x), \end{align*}$

tak więc

${R}(x)\ =\ \frac{c_0+(c_1-a_1c_0)x}{1-a_1x-a_2x^2}$

Dla funkcji ${A}(x)=1-a_1x-a_2x^2=(1-\rho_1x)(1-\rho_2x)$ mogą zajść trzy przypadki:

• $\rho_1 \neq \rho_2$ są różnymi liczbami rzeczywistymi. Wtedy

$r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n,$

gdzie $\alpha$ oraz $\beta$ są liczbami rzeczywistymi.

• $\rho_1 = \rho_2$. Wtedy

$r_n\ =\ (\alpha n+\beta)\rho_1^n,$

gdzie $\alpha$ oraz $\beta$ są liczbami rzeczywistymi.

• $\bigtriangledown$ Wartości $\rho_1$ oraz $\rho_2$ są różnymi liczbami zespolonymi. W tym wypadku całe rozumowanie przeprowadzone wcześniej dla liczb rzeczywistych pozostaje w mocy, tyle że dokonywane jest teraz na liczbach zespolonych. Dostajemy więc

$r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n.$

gdzie $\alpha$ oraz $\beta$ są pewnymi liczbami zespolonymi. Przypadek pierwszy jest więc szczególną sytuacją obecnego przypadku. Może być jednak rozważany bez znajomości liczb zespolonych.

Wracamy teraz do ogólnego, jednorodnego liniowego równania rekurencyjnego. Analogicznie do przypadku, gdy $k=2$, otrzymujemy że

${R}(x)\ =\ \frac{{P}(x)}{1-a_1x-a_2x^2-\ldots-a_kx^k},$

gdzie ${P}(x)$ jest wielomianem co najwyżej stopnia $k-1$, zależnym od wartości $c_0,\ldots,c_{k-1},a_1,\ldots,a_k$. Korzystając z ogólnej metody rozwijania funkcji wymiernej w szereg, możemy odzyskać wyrazy ciągu $r_n$, jako współczynniki $[x^n]{R}(x)$ zgodnie z równaniem (12).

Przykład

Równanie rekurencyjne ma następującą postać

$\left \{ \begin{array} {l} r_0 & = & 0, \\ r_1 & = & 0, \\ r_2 & = & 1, \\ r_n & = & r_{n-1}+r_{n-2}-r_{n-3}\quad\textrm{dla}\ n\geq 3. \end{array}\right .$

Ostatnia zależność prowadzi do funkcji tworzącej ${R}(x)$ spełniającej

${R}(x)=x^2 + x{R}(x) + x^2{R}(x) - x^3{R}(x).$

Po dokonaniu prostego wyliczenia dostajemy:

${R}(x)=\frac{x^2}{1-x-x^2+x^3}.$

W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg, wyliczyliśmy współczynniki $[x^n]{R}(x)$, a zatem mamy:

$r_n=-\frac{1}{4}+\frac{1}{2}(n+1) - \frac{1}{4}(-1)^n\quad\textrm{dla dowolnego}\ n=0,1,2,3,\ldots.$