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) $(g_0,g_1,g_2,g_3,\dots )$ to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) $x$ postaci

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\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 \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 wtedy i tylko wtedy, gdy istnieje stała $M\ge 0$ ograniczająca wszystkie skończone początkowe sumy, tzn.

$\left|g_0\right|+\left|g_{1}x\right|+\left|g_2{x}^2\right|+\dots +\left|g_n{x}^n\right|\le M$

zachodzi dla dowolnego $n\ge 0$. Ponadto jeśli dla pewnej liczby $x_0\in \mathbb{ℝ}$ 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{ℝ}$ spełniającego $\left|x_1\right|\le \left|x_0\right|$. 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 $x<r$, to Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} jest zbieżny;

• jeśli $x>r$, to Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}(x)} jest rozbież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:(-r,r)⟶\mathbb{ℝ},$

o wartościach Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\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 $(g_0,g_1,g_2,\dots )$, 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 $(g_0,g_1,g_2,g_3,\dots )$, 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\ne 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 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 \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 \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 \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 \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 \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{\mathbb{N}}$

${(1+x)}^m=(\genfrac{}{}{0ex}{}{m}{0})x^0+(\genfrac{}{}{0ex}{}{m}{1})x+(\genfrac{}{}{0ex}{}{m}{2})x^2+\dots +(\genfrac{}{}{0ex}{}{m}{m-1})x^{m-1}+(\genfrac{}{}{0ex}{}{m}{m})x^m=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{m}{n})x^n.$

Przyjrzyjmy się teraz rozwinięciu w szereg funkcji ${(1+x)}^y$, gdzie $y\in \mathbb{ℝ}$ 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 $(\genfrac{}{}{0ex}{}{y}{n})$, gdzie $y\in \mathbb{ℝ}$ oraz $n\in \mathbb{\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{\mathbb{N}}$ spełniającego dodatkowo $y\ge n$, uogólniony symbol dwumianowy $(\genfrac{}{}{0ex}{}{y}{n})$ jest liczbą $n$-elementowych podzbiorów zbioru $y$-elementowego.

Twierdzenie 7.4

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

${(1+x)}^y=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{y}{n})x^n.$

Wniosek 7.5

Dla liczby naturalnej $m$ zachodzi

$\frac{1}{{(1-x)}^{m+1}}=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{m+n}{n})x^n.$

Dowód

Dowód zostawiony jest jako ćwiczenie [ex][ex newton for integer].

Przykład

Policzmy sumę

$\sum _{k=0}^n{k}^2=1+4+9+\dots +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 \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 \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ę

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

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

$\frac{1}{{(1-x)}^3}=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+2}{n})x^n=\frac{1}{2}\sum _{n=0}^{\mathrm{\infty }}{n}^2{x}^n+\frac{3}{2}\sum _{n=0}^{\mathrm{\infty }}n{x}^n+\sum _{n=0}^{\mathrm{\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,\dots ,n^2,\dots$:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\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,\dots ,1+4+9+\dots +n^2,\dots$, tzn. ciągu sum początkowych wyrazów ciągu $1,4,9,\dots ,n^2,\dots$. 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 \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}+\dots ,=\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,b_n=a_n+b_{n-5},c_n=b_n+c_{n-10},d_n=c_n+d_{n-25},e_n=d_n+e_{n-50}.$

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

$n$	0	5	10	15	2	25	30	35	40	45	50	55	60	65	70	75	80	85	90	95	100
$a_n$	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
$b_n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
$c_n$	1	2	4	6	9	12	16	10	25	30	36	42	49	56	64	72	81		100		121
$d_n$	1					13					49					121					242
$e_n$	1										50										292

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 $(f_0,f_1,f_2,f_3,\dots )$ 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 \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=1+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-\gold x\right)\left(1-\goldd x\right)} =\frac{1}{\sqrt{5}}\left(\frac{1}{\left(1-\gold x\right)}-\frac{1}{\left(1-\goldd x\right)}\right), }

gdzie Parser nie mógł rozpoznać (nieznana funkcja „\gold”): {\displaystyle \gold=\frac{1+\sqrt{5}}{2}} jest złotą liczbą oraz Parser nie mógł rozpoznać (nieznana funkcja „\goldd”): {\displaystyle \goldd=\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 \fGen{F}(x) =\frac{1}{\sqrt{5}}\left(\sum_{n=1}^{\infty}{\gold^nx^n}-\sum_{n=1}^{\infty}{\goldd^nx^n}\right) =\frac{1}{\sqrt{5}}\sum_{n=1}^{\infty}{\left(\gold^n-\goldd^n\right)x^n}. }

Tak więc dostajemy szybko znaną nam już postać zwartą Parser nie mógł rozpoznać (nieznana funkcja „\gold”): {\displaystyle f_n=\frac{1}{\sqrt{5}}\left(\gold^n-\goldd^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\ne 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.

Dowód [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\ne 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 \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

$\frac{1}{{(1-\rho x)}^{m+1}}=\sum _{n=1}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{m+n}{m}){\rho }^n{x}^n$

i w konsekwencji:

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

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

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,\dots ,{\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.