Matematyka dyskretna 1/Wykład 7: Funkcje tworzące

Przykład

Słynny matematyk Georg Pólya rozważał problem polegający na policzeniu wszystkich możliwych sposobów, na które można rozmienić 50 centów używając jednocentówek $(1)$, pięciocentówek $(5)$, dziesięciocentówek $(10)$, ćwierćdolarówek $(25)$, oraz półdolarówki $(50)$. Rozważania te doprowadziły go do użycia analitycznych metod funkcji tworzących w zaproponowanym przez niego rozwiązaniu. W tym i następnym wykładzie poznamy te metody i zobaczymy jak mogą być pomocne w zliczaniu rożnych obiektów kombinatorycznych.

Wracając do problemu rozmieniania monet, wygodnie nam będzie posiadać jeszcze monetę $[0]$, którą możemy interpretować jako brak monet. Wypiszmy teraz (nadużywając trochę notacji) nieskończoną sumę wszystkich możliwości rozmiany dowolnej kwoty za pomocą jednocentówek

Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle A_1=[0]+\moneta(1)+\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\ldots }

i analogicznie przeanalizujmy sumę dla pieciocentówek

Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle A_5=[0]+\moneta(5)+\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)\moneta(5)+\ldots }

Wtedy zbiór par $A_{1}\times A_{5}$ jest zbiorem wszystkich możliwości rozmiany kwoty mając do dyspozycji dowolnie wiele jednocentówek oraz pięciocentówek.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned B= A_1 \times A_5 &=\left([0]+\moneta(1)+\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\ldots\right)\\ &\times\left([0]+\moneta(5)+\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)\moneta(5)+\ldots\right)\\ &=[0]+\moneta(1)+\moneta(5)+\moneta(1)\moneta(1)+\moneta(1)\moneta(5)+\moneta(5)\moneta(5)+\moneta(1)\moneta(1)\moneta(1)+\ldots \endaligned}

Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} , ćwierćdolarówek Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} , oraz półdolarówek Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} wyglądają następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned A_{10} &= [0]+\moneta(10)+\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)\moneta(10)+\ldots\\ A_{25} &= [0]+\moneta(25)+\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)\moneta(25)+\ldots\\ A_{50} &= [0]+\moneta(50)+\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)\moneta(50)+\ldots. \endaligned}

Dodając kolejno monety Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} , i na końcu Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} do możliwych rozmian uzyskujemy odpowiednio:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned C&=B\times\left([0]+\moneta(10)+\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)\moneta(10)+\ldots\right)\\ D&=C\times\left([0]+\moneta(25)+\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)\moneta(25)+\ldots\right)\\ E&=D\times\left([0]+\moneta(50)+\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)\moneta(50)+\ldots\right)\\ &=[0]+\moneta(1)+\moneta(5)+\moneta(10)+\moneta(25)+\moneta(50)+\moneta(1)\moneta(1)+\moneta(1)\moneta(5)+\moneta(1)\moneta(10)+\ldots \endaligned}

Grupując teraz składniki sumy $E$ w podsumy o tych samych wartościach dostajemy wyrażenie:

Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \begin{array} {rcl} E&=&\big(\moneta(1)\big)+\big(\moneta(1)\moneta(1)\big)+\big(\moneta(1)\moneta(1)\moneta(1)\big)+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\big)\\ &&+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\moneta(5)\big)\\ &&+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\moneta(5)\moneta(1)\big)+\ldots \end{array} }      (1)

Zliczając zaś tylko składniki w podsumie odpowiadającej wartości $n$ centów, otrzymujemy liczbę sposobów, na które można rozmienić $n$ centów przy użyciu monet Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(1)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(5)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} , oraz Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} . Pomysłem pochodzącym od Pólya, było zastąpienie monety Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(1)} przez zmienną $x$, monety Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(5)} przez $x\cdot x\cdot x\cdot x\cdot x=x^{5}$ i analogicznie Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} przez $x^{10}$, Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} przez $x^{25}$, oraz Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} przez $x^{50}$. Uzyskujemy w ten sposób nieskończony szereg zmiennej $x$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{E}(x)&=\left(1+x+x^2+x^3\ldots\right)\cdot\left(1+x^5+x^{10}+x^{15}\ldots\right)\cdot\left(1+x^{10}+x^{20}+x^{30}\ldots\right)\\ &\cdot\left(1+x^{25}+x^{50}+x^{75}\ldots\right)\cdot\left(1+x^{50}+x^{100}+x^{150}\ldots\right)\\ &=1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+2x^9+4x^{10}+\ldots \endaligned}

Godne zauważenia jest, że liczba różnych możliwych sposobów rozmiany $n$ centów (równa liczbie grup monet w odpowiednim nawiasie we wzorze (1)) jest równa współczynnikowi stojącemu przy jednomianie $x^{n}$.

Funkcja tworząca Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} dla ciągu liczb rzeczywistych (lub zespolonych) $\left(g_{0},g_{1},g_{2},g_{3},\ldots \right)$ to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) $x$ postaci

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots. }

Na oznaczenie współczynnika $n$-tego wyrazu szeregu Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} używać będziemy oznaczenia Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\displaystyle \vect{x^n}\fGen{G}(x)=g_n} .

Uwaga Jak traktowac funkcje tworzące

Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}} . Z wykładu Analiza Matematyczna wiemy, że szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} jest zbieżny, jeśli istnieje stała $M\geq 0$ ograniczająca wszystkie skończone początkowe sumy, tzn.

$\left\vert g_{0}\right\vert +\left\vert g_{1}x\right\vert +\left\vert g_{2}x^{2}\right\vert +\ldots +\left\vert g_{n}x^{n}\right\vert \leq M$

zachodzi dla dowolnego $n\geq 0$. Ponadto jeśli dla pewnej liczby $x_{0}\in \mathbb {R}$ szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x_0)=g_0+g_1x_0+g_2x_0^2+\ldots} jest zbieżny, to i także szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x_1)=g_0+g_1x_1+g_2x_1^2+\ldots} jest zbieżny dla dowolnego $x_{1}\in \mathbb {R}$ spełniającego $\left\vert x_{1}\right\vert \leq \left\vert x_{0}\right\vert$. Możemy więc określić promień zbieżności szeregu jako taką liczbę Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\displaystyle r\in\mathbb{R}_*\cup{\left\{ {\infty} \right\}\ }=\vect{0,+\infty}} , że jeśli Parser nie mógł rozpoznać (nieznana funkcja „\righ”): {\displaystyle \left\vert x\righ\vert<r} , to Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} jest zbieżny.

Szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots} można więc potraktować jako funkcję

$G:\left(-r,r\right)\longrightarrow \mathbb {R} ,$

o wartościach Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{G}(x)=\lim_{n\rightarrow\infty}{\left(g_0+g_1x+g_2x^2+\ldots+g_nx^n\right)}.} Oczywiście Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(0)=g_0} , więc dla $x=0$ szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} jest zbieżny.

Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots} jako formę zapisu ciągu $\left(g_{0},g_{1},g_{2},\ldots \right)$, czyli jedynie jako ciąg symboli. Równości pomiędzy odpowiednimi wzorami służą rozwiązaniu problemów kombinatorycznych, tak więc traktujemy je jako równości dwu wyrażeń, a nie jako równość dwu funkcji rzeczywistych, pomimo że mają one uzasadnienia w języku analizy matematycznej.

Jak zobaczymy na wielu przykładach, funkcje tworzące są bardzo użytecznym narzędziem przy wyznaczaniu wartości elementów ciągu. Jeśli bowiem Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots} jest funkcją tworzącą ciągu $\left(g_{0},g_{1},g_{2},g_{3},\ldots \right)$, oraz w jakiś sposób będziemy w stanie poznać postać zwartą funkcji $G(x)$, to rozwijając tę postać zwartą w szereg Taylora, poznamy kolejne współczynniki tego rozwinięcia. A współczynniki te, to właśnie kolejne wyrazy naszego ciągu.

Będziemy się zajmowali jedynie tymi funkcjami, dla których promień zbieżności $r>0$. Ponadto będziemy pomijać problem zbieżności oraz wartość $r$ promienia zbieżności, skupiając się jedynie na przekształceniach wzorów. Poniżej zebrane zostały te własności, które często wykorzystywane są w takich przekształceniach.

Obserwacja 7.1

Dla dwu funkcji tworzących Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}(x)=f_0+f_1x+f_2x^2+\ldots} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots} mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{F}(x)=\fGen{G}{x}&\Leftrightarrow f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots\\ &&\\ \alpha\cdot\fGen{F}(x)+\beta\cdot\fGen{G}{x}&= \sum_{n=0}^{\infty}{\left(\alpha\cdot f_n+\beta\cdot g_n\right)x^n}\\ &=\left(\alpha\cdot f_0+\beta\cdot g_0\right) + \left(\alpha\cdot f_1+\beta\cdot g_1\right)x + \left(\alpha\cdot f_2+\beta\cdot g_2\right)x^2 + \ldots\\ &&\\ \fGen{F}(x)\cdot\fGen{G}(x)&=\sum_{n=0}^{\infty}\left(\sum_{k=0}^n f_k g_{n-k}\right) x^n\\ &= f_0g_0 + \left(f_0g_1+f_1g_0\right)x\\ & + \left(f_0g_2+f_1g_1+f_2g_0\right)x^2\\ & + \left(f_0g_3+f_1g_2+f_2g_1+f_3g_0\right)x^3+\ldots\\ \endaligned}

Wyrażenie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}(x)\cdot\fGen{G}(x)} nazywać będziemy splotem szeregów Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}(x)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} .

Twierdzenie 7.2

Funkcja tworząca postaci

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)=g_0+g_1x+g_2x^2+g_3x^3+\ldots }

ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{U}(x)} taka, że Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{U}(x)\fGen{G}(x)=1} , wtedy i tylko wtedy, gdy $g_{0}\neq 0$.

Następne własności są bardzo pomocne w dokonywanych przekształceniach funkcji tworzących.

Obserwacja 7.3

Dla dwu funkcji tworzących Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}(x)=f_0+f_1x+f_2x^2+\ldots} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots} mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle x^m\fGen{G}(x)&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots}      (2)

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \frac{\fGen{G}(x)-\sum_{i=0}^{m-1}{g_ix^i}}{x^{m}}&=&g_m+g_{m+1}x+g_{m+2}x^{2}+g_{m+3}x^{3}+g_{m+4}x^{4}+\ldots}      (3)

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{G}(\alpha x)&=&g_0+g_1\alpha x+g_2\alpha^2x^2+g_3\alpha^3x^3+g_4\alpha^4x^4+\ldots}      (4)

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{G'}(x)&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots}      (5)

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \int \fGen{G}(x)dx &=& 0+g_0x+\frac{1}{2}g_1x^2+\frac{1}{3}g_2x^3+\frac{1}{4}g_3x^4+\ldots}      (6)

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \frac{\fGen{G}(x)}{1-x}&=&g_0+\left(g_0+g_1\right)x+\left(g_0+g_1+g_2\right)x^2+\ldots}      (7)

Funkcje tworzące w zliczaniu

Widzieliśmy już, że dla $n\in \mathbb {N}$

$\displaystyle \left(1+x\right)^{m}={m \choose 0}x^{0}+{m \choose 1}x+{m \choose 2}x^{2}+\ldots +{m \choose m-1}x^{m-1}+{m \choose m}x^{m}=\sum _{n=0}^{m}{m \choose n}x^{n}.$

Przyjrzyjmy się teraz rozwinięciu w szereg funkcji $\left(1+x\right)^{y}$, gdzie $y\in \mathbb {R}$ jest parametrem. Rozwinięcie takie okaże się bardzo przydatne w rozwiązywaniu wielu przykładów. Aby poznać ciąg odpowiadający tej funkcji wprowadźmy definicję.

Uogólniony symbol dwumianowy ${y \choose n}$, gdzie $y\in \mathbb {R}$ oraz $n\in \mathbb {N}$ jest oznaczeniem na

Parser nie mógł rozpoznać (błąd składni): {\displaystyle { y \choose n }\ =\ \frac{y^{\underline{n}}}{n!}\ =\ \frac{y\cdot\left(y-1\right)\cdot\ldots\cdot\left(y-\left(n-1\right)\right)}{1\cdot2\cdot\ldots\cdot\left(n-1\right)\cdot n}. }

Uwaga

Oczywiście dla $y\in \mathbb {N}$ spełniającego dodatkowo $y\geq n$, uogólniony symbol dwumianowy ${y \choose n}$ jest liczbą $n$-elementowych podzbiorów zbioru $y$-elementowego.

Twierdzenie 7.4

Dla liczby rzeczywistej $y$ oraz liczby naturalnej $n$ zachodzi

$\displaystyle \left(1+x\right)^{y}=\sum _{n=0}^{\infty }{y \choose n}x^{n}.$

Wniosek 7.5

Dla liczby naturalnej $m$ zachodzi

$\displaystyle {\frac {1}{\left(1-x\right)^{m+1}}}=\sum _{n=0}^{\infty }{m+n \choose n}x^{n}.$

Dowód

Dowód zostawiony jest jako ćwiczenie 3.

Przykład

Policzmy sumę

$\displaystyle \sum _{k=0}^{n}k^{2}=1+4+9+\ldots +n^{2}.$

Zacznijmy od znalezienia zwartej postaci funkcji tworzącej

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}n^2x^n} . Korzystając z Wniosku 7.5 otrzymujemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{1}{1-x}&=&\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,}      (8)

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{1}{\left(1-x\right)^2}&=&\sum_{n=0}^{\infty}{n+1 \choose n }x^n\ =\ \sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n. }      (9)

Po przekształceniu równości (9) uzyskuje się

$\displaystyle \sum _{n=0}^{\infty }nx^{n}={\frac {1}{\left(1-x\right)^{2}}}-{\frac {1}{1-x}}.$      (10)

Powołując się ponownie na Wniosek 7.5 otrzymujemy

$\displaystyle {\frac {1}{\left(1-x\right)^{3}}}=\sum _{n=0}^{\infty }{n+2 \choose n}x^{n}={\frac {1}{2}}\sum _{n=0}^{\infty }n^{2}x^{n}+{\frac {3}{2}}\sum _{n=0}^{\infty }nx^{n}+\sum _{n=0}^{\infty }x^{n},$

co w połączeniu z równościami (9) oraz (10) daje zwartą postać funkcji tworzącej Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} dla ciągu $1,4,9,\ldots ,n^{2},\ldots$:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}n^2x^n =\frac{2}{\left(1-x\right)^3}-\frac{3}{\left(1-x\right)^2}+\frac{1}{1-x}. }

Naszym zadaniem było jednakże policzenie funkcji tworzącej $H(x)$ dla ciągu $1,1+4,1+4+9,\ldots ,1+4+9+\ldots +n^{2},\ldots$, tzn. ciągu sum początkowych wyrazów ciągu $1,4,9,\ldots ,n^{2},\ldots$. Aby uzyskać Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{H}(x)} wystarczy więc skorzystać ze wzoru (7) i podzielić Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} przez $1-x$. Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{H}(x)=\frac{\fGen{G}(x)}{1-x} =\frac{2}{\left(1-x\right)^4}-\frac{3}{\left(1-x\right)^3}+\frac{1}{\left(1-x\right)^2}. }

Korzystając po raz kolejny z Wniosku 7.5 otrzymujemy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{H}(x) &=2\sum_{n=0}^{\infty}{n+3 \choose n}x^n-3\sum_{n=0}^{\infty}{n+2 \choose n}x^n+\sum_{n=0}^{\infty}{n+1 \choose n}x^n\\ &=\sum_{n=0}^{\infty}\left(\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n\right)x^n. \endaligned}

W konsekwencji zachodzi równość

Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\displaystyle \displaystyle \sum_{k=1}^nk^2=\vect{x^n}\fGen{H}(x)=\frac{2n^3+3n+n}{6}. }

Przykład

Wracamy do przykładu z monetami. Występowały tam funkcje tworzące postaci

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{A_k}(x) = 1+x^k+x^{2k}+x^{3k}+\ldots, }

dla $k=1,5,10,25$ i $50$. Z równości (7) wiemy, że

$1+x^{k}+x^{2k}+x^{3k}+\ldots ,={\frac {1}{1-x^{k}}}$

tak więc:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{A}(x)= \fGen{A_1}(x)&= \frac{1}{1-x},\\ \fGen{B}(x)= \fGen{A}(x)\cdot \fGen{A_5}(x) &=\frac{\fGen{A}(x)}{1-x^5},\\ \fGen{C}(x)= \fGen{B}(x)\cdot \fGen{A_{10}}(x) &=\frac{\fGen{B}(x)}{1-x^{10}},\\ \fGen{D}(x)= \fGen{C}(x)\cdot \fGen{A_{25}}(x) &=\frac{\fGen{C}(x)}{1-x^{25}},\\ \fGen{E}(x)= \fGen{D}(x)\cdot \fGen{A_{50}}(x) &=\frac{\fGen{D}(x)}{1-x^{50}}, \endaligned}

skąd natychmiast:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{A}(x)&=1+x\fGen{A}(x),\\ \fGen{B}(x)&=\fGen{A}(x)+x^5\fGen{B}(x),\\ \fGen{C}(x)&=\fGen{B}(x)+x^{10}\fGen{C}(x),\\ \fGen{C}(x)&=\fGen{D}(x)+x^{25}\fGen{C}(x),\\ \fGen{D}(x)&=\fGen{E}(x)+x^{50}\fGen{D}(x). \endaligned}

Równości te dają zależności między współczynnikami:

$a_{n}=1,\quad b_{n}=a_{n}+b_{n-5},\quad c_{n}=b_{n}+c_{n-10},\quad d_{n}=c_{n}+d_{n-25},\quad$$\quad e_{n}=d_{n}+e_{n-50}.$

Wykorzystując te zależności rekurencyjne możemy wypełnić następującą tabelę:

Parser nie mógł rozpoznać (nieznana funkcja „\array”): {\displaystyle \array{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 5 & 10 & 15 & 2 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80 & 85 & 90 & 95 & 100\\ \hline\hline a_n & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline b_n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21\\ \hline c_n & 1 & 2 & 4 & 6 & 9 & 12 & 16 & 10 & 25 & 30 & 36 & 42 & 49 & 56 & 64 & 72 & 81 & & 100 & & 121\\ \hline d_n & 1 & & & & & 13 & & & & & 49 & & & & & 121 & & & & & 242\\ \hline e_n & 1 & & & & & & & & & & 50 & & & & & & & & & & 292\\ \hline \endarray }

Pół dolara można rozmienić na $50$ sposobów. Z kolei rozmieniać jednego dolara można na aż $292$ sposoby. Do problemu tego wrócimy jeszcze w następnym wykładzie.

Funkcje tworzące w rozwiązywaniu zależności rekurencyjnych

Przykład

Rozważmy ciąg Fibonacci'ego, tzn. ciąg $\left(f_{0},f_{1},f_{2},f_{3},\ldots \right)$ zdefiniowany w następujący sposób:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned f_0&=0,\\ f_1&=1,\\ f_n&=f_{n-1}+f_{n-2}\quad\textrm{dla}\ n\geq 2. \endaligned}

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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}(x)} dla ciągu Fibonacci'ego

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{F}(x) =\sum_{n=0}^{\infty}f_nx^n =x+\sum_{n=2}^{\infty}\left(f_{n-1}+f_{n-2}\right)x^n=x+x\fGen{F}(x)+x^2\fGen{F}(x). }

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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}(x)=\frac{x}{1-x-x^2} =\frac{x}{\left(1-z_0 x\right)\left(1-z_1 x\right)} =\frac{1}{\sqrt{5}}\left(\frac{1}{\left(1-z_0 x\right)}-\frac{1}{\left(1-z_1 x\right)}\right), }

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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{F}(x) =\frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty}{{z_0}^nx^n}-\sum_{n=0}^{\infty}{{z_1}^nx^n}\right) =\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}{\left({z_0}^n-{z_1}^n\right)x^n}. }

Tak więc dostajemy szybko znaną nam już postać zwartą $f_{n}={\frac {1}{\sqrt {5}}}\left({z_{0}}^{n}-{z_{1}}^{n}\right)$.

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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{P}(x)}=n} , jeśli Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{P}(x)=p_0+p_1x+\ldots+p_nx^n} .

Funkcja wymierna Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)} to funkcja postaci Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \frac{\fGen{P}(x)}{\fGen{Q}(x)}} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{P}(x)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)\neq0} są wielomianami skończonego stopnia.

Obserwacja 7.6

Niech $A(x)$ oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{B}(x)} będą wielomianami Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{A}(x)}\geq deg{\fGen{B}(x)}} . Wtedy istnieją wielomiany Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)} takie, że

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{A}(x)=\fGen{Q}(x)\fGen{B}(x)+\fGen{R}(x), }

gdzie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{R}(x)}< deg{\fGen{A}(x)}=deg{\fGen{Q}(x)}+deg{\fGen{B}(x)}} .

Przykład

Niech

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{A}(x)=3x^5+5x^4+2x^3+x^2+2\quad\textrm{oraz}\quad\fGen{B}(x)=x^3+2x^2-1.}

Wtedy wielomiany

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)=3x^2-x+3\quad\textrm{oraz}\quad\fGen{R}(x)=x+2 }

spełniają

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{A}(x)}&=3x^5+5x^4+2x^3+x^2+2\\ &=\left(3x^2-x+3\right)\cdot\left(x^3+2x^2-1\right)+x+2\\ &=\fGen{Q}(x)\fGen{B}(x)+\fGen{R}(x). \endaligned}

Ponadto Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{A}(x)}=5=2+3=deg{\fGen{Q}(x)}+deg{\fGen{B}(x)}} .

Wniosek 7.7

Niech Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{P}(x)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)} będą wielomianami takimi, że Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{P}(x)}\geq deg{\fGen{Q}(x)}} . Wtedy funkcję wymierną Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\fGen{P}(x)/ \fGen{Q}(x),} można przedstawić w postaci

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\fGen{A}(x)+\frac{\fGen{B}(x)}{\fGen{Q}(x)}, }

dla pewnych wielomianów Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{A}(x)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{B}(x)}

spełniających Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{B}(x)}<deg{\fGen{Q}(x)}} .

Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\fGen{P}(x)/\fGen{Q}(x), } dla których Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}} .

Twierdzenie 7.8

Niech Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{P}(x)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)} będą wielomianami takimi, że

• Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}} ,

• Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)=\fGen{S}(x)\fGen{T}(x)} , gdzie oba wielomiany Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{S}(x),\fGen{T}(x)} są stopnia co najmniej $2$,

• $q_{0}\neq 0$.

Wtedy istnieją wielomiany Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{A}(x)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{B}(x)} takie, że Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{A}(x)}<deg{\fGen{S}(x)}} i Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{B}(x)}<deg{\fGen{T}(x)}} oraz

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \frac{\fGen{P}(x)}{\fGen{Q}(x)} =\frac{\fGen{A}(x)}{\fGen{S}(x)}+\frac{\fGen{B}(x)}{\fGen{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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}, }

gdzie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}} , oraz $q_{0}\neq 0$. Załóżmy ponadto, że wielomian Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)} rozkłada się na następujący iloczyn czynników liniowych

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x) =q_0\left(1-\rho_1x\right)^{m_1}\cdot\left(1-\rho_2x\right)^{m_2}\cdot\ldots\cdot\left(1-\rho_kx\right)^{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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{P_1}(x),\ldots,\fGen{P_k}(x)} takie, że

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x) =\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\frac{\fGen{P_1}(x)}{\left(1-\rho_1x\right)^{m_1}}+\frac{\fGen{P_2}(x)}{\left(1-\rho_2x\right)^{m_2}}+\ldots+\frac{\fGen{P_k}(x)}{\left(1-\rho_kx\right)^{m_k}}, }

gdzie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle deg{\fGen{P_i}(x)}<m_i} . Na mocy Obserwacji 7.6 możemy sprowadzić wielomian Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{P_i}(x)} do

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{P_i}(x)&=\fGen{P_i^1}(x)\left(1-\rho_ix\right)+\gamma_{m_i}\\ &=\fGen{P_i^2}(x)\left(1-\rho_ix\right)^2+\gamma_{m_i-1}\left(1-\rho_ix\right)+\gamma_{m_i}\\ &\vdots\\ &=\gamma_1\left(1-\rho_ix\right)^{m_i-1}+\ldots+\gamma_{m_i-1}\left(1-\rho_ix\right)+\gamma_{m_i}, \endaligned}

gdzie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle m_i\geq deg{\fGen{P_i}(x)}>deg{\fGen{P_i^1}(x)}>deg{\fGen{P_i^2}(x)}>\ldots} . W konsekwencji otrzymamy

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle \fGen{R}(x)\ =\ \sum_{i=1}^k{\left(\frac{\gamma_{i,1}}{1-\rho_ix}+\frac{\gamma_{i,2}}{\left(1-\rho_ix\right)^2}+\ldots+\frac{\gamma_{i,m_i}}{\left(1-\rho_ix\right)^{m_i}}\right)}. }

Mnożąc teraz obie strony przez

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)/q_0=\left(1-\rho_1x\right)^{m_1}\cdot\left(1-\rho_2x\right)^{m_2}\cdot\ldots\cdot\left(1-\rho_kx\right)^{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}{\left(1-\rho x\right)^{m+1}}}=\sum _{n=1}^{\infty }{{m+n \choose m}\rho ^{n}x^{n}}$

i w konsekwencji:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \displaystyle [x^n]\fGen{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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x) =\frac{x^2}{\left(1-x\right)^2\cdot\left(1+x\right)}=\frac{\alpha}{1-x}+\frac{\beta}{\left(1-x\right)^2}+\frac{\gamma}{1+x}. }

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

$x^{2}=\alpha \left(1-x^{2}\right)+\beta \left(1+x\right)+\gamma \left(1-2x+x^{2}\right).$

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\lbrace {\begin{array}{rrrcl}\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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{R}(x)&=\sum_{n=0}^{\infty}\left(-\frac{1}{4}+\frac{1}{2}\left(n+1\right) - \frac{1}{4}\left(-1\right)^n\right)x^n\\ &=x^2+x^3+2x^4+2x^5+3x^6+3x^7+4x^8+\ldots. \endaligned}

Jeżeli mianownik Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)} funkcji wymiernej Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}} posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)} na sumę.

Twierdzenie 7.9

Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\fGen{P}(x)/\fGen{Q}(x)} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)=q_0\cdot\left(1-\rho_1x\right)\cdot\ldots\cdot\left(1-\rho_1x\right)} i liczby $\rho _{1},\ldots ,\rho _{l}$ są parami różne, to w przypadku gdy Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{P}(x)} jest wielomianem stopnia mniejszego niż $l$, zachodzi

Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\displaystyle \vect{x^n}\fGen{R}(x) =a_1\rho_1^n+\ldots+a_l\rho_l^n, \quad\textrm{dla}\ a_k=\frac{-\rho_k\cdot\fGen{P}(1/\rho_k)}{\fGen{Q'}(1/\rho_k)}. }

Przykład

Mianownik Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{Q}(x)} funkcji wymiernej

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\frac{2x}{1-5x-2x^2+24x^3}. }

ma trzy różne pierwiastki i można Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)} przedstawić jako

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=\frac{2x}{\left(1+2x\right)\left(1-3x\right)\left(1-4x\right)}. }

Na mocy Twierdzenia 7.9 otrzymujemy więc, że

Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\displaystyle \vect{x^n}\fGen{R}(x)=-\frac{2}{15}\left(-2\right)^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 rekurencyjne to równanie postaci

$\left\lbrace {\begin{array}{rcl}r_{0}&=&c_{0},\\&\cdots &\\r_{k-1}&=&c_{k-1},\\r_{n}&=&a_{1}r_{n-1}+a_{2}r_{n-2}+\ldots +a_{k}r_{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\lbrace {\begin{array}{rcl}r_{0}&=&c_{0},\\r_{1}&=&c_{1},\\r_{n}&=&a_{1}r_{n-1}+a_{2}r_{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 $\left(r_{0},r_{1},r_{2},\ldots \right)$ daje:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\fGen{R}(x)&=r_0+r_1x+r_2x^2+r_3x^3+\ldots+r_nx^n+\ldots\\ &=c_0+c_1x+\left(a_1r_1+a_2r_0\right)x^2+\ldots+\left(a_1r_{n-1}+a_2r_{n-2}\right)x^n+\ldots\\ &=c_0+\left(c_1-a_1c_0\right)x+a_1x\fGen{R}(x)+a_2x^2\fGen{R}(x), \endaligned}

tak więc

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)\ =\ \frac{c_0+\left(c_1-a_1c_0\right)x}{1-a_1x-a_2x^2} }

Dla funkcji Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{A}(x)=1-a_1x-a_2x^2=\left(1-\rho_1x\right)\left(1-\rho_2x\right)} 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}\ =\ \left(\alpha n+\beta \right)\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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)\ =\ \frac{\fGen{P}(x)}{1-a_1x-a_2x^2-\ldots-a_kx^k}, }

gdzie Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle [x^n]\fGen{R}(x)} zgodnie z równaniem (12).

Przykład

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

$\left\lbrace {\begin{array}{rcl}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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)} spełniającej

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{R}(x)=x^2 + x\fGen{R}(x) + x^2\fGen{R}(x) - x^3\fGen{R}(x). }

Po dokonaniu prostego wyliczenia dostajemy:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle [x^n]\fGen{R}(x)} , a zatem mamy:

$r_{n}=-{\frac {1}{4}}+{\frac {1}{2}}\left(n+1\right)-{\frac {1}{4}}\left(-1\right)^{n}\quad {\textrm {dladowolnego}}\ n=0,1,2,3,\ldots .$