Test Arka

Problemy ze wzorami na osiłku

$M$ $M^{\prime }$ $M^{\prime }$ Parser nie mógł rozpoznać (nieznana funkcja „\large”): {\displaystyle {\large a^{\sum_{i=1}^{10}i}}}

A powinno to wyglądać tak: http://www.ii.uj.edu.pl/~pawlik1/MediaWiki

---

Konwersja Arka Konwersja Arka 2 Konwersja Arka 3

---

{thm}{Twierdzenie} {obs}[thm]{Obserwacja} {con}[thm]{Wniosek}

{article} {../makraB}

Funkcje tworzące

Przykład [Uzupelnij]

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 $\left(1\right)$, pięciocentówek $\left(5\right)$, dziesięciocentówek $\left(10\right)$, ćwierćdolarówek $\left(25\right)$, oraz półdolarówki $\left(50\right)$. 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ę $\left[0\right]$, 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

$A_1=\left[0\right]+\left(1\right)+\left(1\right)\left(1\right)+\left(1\right)\left(1\right)\left(1\right)+\left(1\right)\left(1\right)\left(1\right)\left(1\right)+\dots$

i analogicznie przeanalizujmy sumę dla pieciocentówek

$A_5=\left[0\right]+\left(5\right)+\left(5\right)\left(5\right)+\left(5\right)\left(5\right)\left(5\right)+\left(5\right)\left(5\right)\left(5\right)\left(5\right)+\dots$

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( \left[0\right]+\left( 1 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots \right)\\ &&\times\left( \left[0\right]+\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)\left( 5 \right)+\ldots \right)\\ &=&\left[0\right]+\left( 1 \right)+\left( 5 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots \endaligned}

Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek $\left(10\right)$, ćwierćdolarówek $\left(25\right)$, oraz półdolarówek $\left(50\right)$ wyglądają następująco:

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

Dodając kolejno monety $\left(10\right)$, $\left(25\right)$, i na końcu $\left(50\right)$ do możliwych rozmian uzyskujemy odpowiednio:

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

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

$\begin{array}{rcl}E& =& \left(\left(1\right)\right)+\left(\left(1\right)\left(1\right)\right)+\left(\left(1\right)\left(1\right)\left(1\right)\right)+\left(\left(1\right)\left(1\right)\left(1\right)\left(1\right)\right)\\ & & +(\left(1\right)\left(1\right)\left(1\right)\left(1\right)\left(1\right)+\left(5\right))\\ & & +(\left(1\right)\left(1\right)\left(1\right)\left(1\right)\left(1\right)\left(1\right)+\left(5\right)\left(1\right))+\dots \end{array}$

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 $\left(1\right)$, $\left(5\right)$, $\left(10\right)$, $\left(25\right)$, oraz $\left(50\right)$. Pomysłem pochodzącym od Pólya, było zastąpienie monety $\left(1\right)$ przez zmienną $x$, monety $\left(5\right)$ przez $x\cdot x\cdot x\cdot x\cdot x=x^5$ i analogicznie $\left(10\right)$ przez $x^{10}$, $\left(25\right)$ przez $x^{25}$, oraz $\left(50\right)$ przez $x^{50}$. Uzyskujemy w ten sposób nieskończony szereg zmiennej $x$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned E\!\left( x \right)&=&\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 (Uzupelnic int wzor S|)) jest równa współczynnikowi stojącemu przy jednomianie $x^n$.

Funkcja tworząca $G\left(x\right)$ 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

$G\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{g}_n{x}^n=g_0+g_{1}x+g_2{x}^2+g_3{x}^3+g_4{x}^4+\dots .$

Na oznaczenie współczynnika $n$-tego wyrazu szeregu $G\left(x\right)$ używać będziemy oznaczenia $\left[x^n\right]G\left(x\right)=g_n$.

Uwaga [Uzupelnij]

Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie $G\left(x\right)$ jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu $G\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{g}_n{x}^n$. Z wykładu Analiza Matematyczna wiemy, że szereg $G\left(x\right)$ 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 $G\left(x_0\right)=g_0+g_1{x}_0+g_2{x}_0^2+\dots$ jest zbieżny, to i także szereg $G\left(x_1\right)=g_0+g_1{x}_1+g_2{x}_1^2+\dots$ 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ę $r\in {\mathbb{ℝ}}_{*}\cup \left\{\mathrm{\infty }\right\}=[0,+\mathrm{\infty }]$, że

• jeśli $x<r$, to $G\left(x\right)$ jest zbieżny;

• jeśli $x>r$, to $G\left(x\right)$ jest rozbieżny.

Szereg $G\left(x\right)=g_0+g_{1}x+g_2{x}^2+\dots$ można więc potraktować jako funkcję

$G:(-r,r)⟶\mathbb{ℝ},$

o wartościach $G\left(x\right)=\underset{n\to \mathrm{\infty }}{\lim }(g_0+g_{1}x+g_2{x}^2+\dots +g_n{x}^n).$ Oczywiście $G\left(0\right)=g_0$, więc dla $x=0$ szereg $G\left(x\right)$ jest zbieżny.

Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg $G\left(x\right)=g_0+g_{1}x+g_2{x}^2+\dots$ 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 $G\left(x\right)=g_0+g_{1}x+g_2{x}^2+\dots$ 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 [Uzupelnij]

Dla dwu funkcji tworzących $F\left(x\right)=f_0+f_{1}x+f_2{x}^2+\dots$ oraz $G\left(x\right)=g_0+g_{1}x+g_2{x}^2+\dots$ mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned F\!\left( x \right)= G\!\left( x \right)&\Leftrightarrow& f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots\\ &&\\ \alpha\cdot F\!\left( x \right)+\beta\cdot G\!\left( x \right)&=& \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\\ &&\\ F\!\left( x \right)\cdot G\!\left( x \right)&=&\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 $F\left(x\right)\cdot G\left(x\right)$ nazywać będziemy splotem szeregów $F\left(x\right)$ oraz $G\left(x\right)$.

Twierdzenie [Uzupelnij]

Funkcja tworząca postaci

$G\left(x\right)=g_0+g_{1}x+g_2{x}^2+g_3{x}^3+\dots$

ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca $U\left(x\right)$ taka, że $U\left(x\right)G\left(x\right)=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 [Uzupelnij]

Dla dwu funkcji tworzących $F\left(x\right)=f_0+f_{1}x+f_2{x}^2+\dots$ oraz $G\left(x\right)=g_0+g_{1}x+g_2{x}^2+\dots$ mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x^m G\!\left( x \right)&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots\\ \frac{ G\!\left( x \right)-\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\\ G\!\left( \alpha x \right)&=&g_0+g_1\alpha x+g_2\alpha^2x^2+g_3\alpha^3x^3+g_4\alpha^4x^4+\ldots\\ G'\!\left( x \right)&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots\\ \int G\!\left( x \right)dx &=& 0+g_0x+\frac{1}{2}g_1x^2+\frac{1}{3}g_2x^3+\frac{1}{4}g_3x^4+\ldots\\ \frac{ G\!\left( x \right)}{1-x}&=&g_0+\left( g_0+g_1 \right)x+\left( g_0+g_1+g_2 \right)x^2+\ldots \endaligned}

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 [Uzupelnij]

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 [Uzupelnij]

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

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

Wniosek [Uzupelnij]

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 [Uzupelnij]

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

Przykład [Uzupelnij]

Policzmy sumę

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

Zacznijmy od znalezienia zwartej postaci funkcji tworzącej $G\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{n}^2{x}^n$. Korzystając z Wniosku Uzupelnic con newton for integer| otrzymujemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \frac{1}{1-x}&=&\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,\\ \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. \endaligned}

Po przekształceniu równości (Uzupelnic eq 11|) uzyskuje się

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

Powołując się ponownie na Wniosek Uzupelnic con newton for integer| 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 (Uzupelnic eq 11|) oraz (Uzupelnic eq 122|) daje zwartą postać funkcji tworzącej $G\left(x\right)$ dla ciągu $1,4,9,\dots ,n^2,\dots$:

$G\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{n}^2{x}^n=\frac{2}{{(1-x)}^3}-\frac{3}{{(1-x)}^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ć $H\left(x\right)$ wystarczy więc skorzystać ze wzoru (Uzupelnic eq 1 przez 1-x|) i podzielić $G\left(x\right)$ przez $1-x$. Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej

$H\left(x\right)=\frac{G\left(x\right)}{1-x}=\frac{2}{{(1-x)}^4}-\frac{3}{{(1-x)}^3}+\frac{1}{{(1-x)}^2}.$

Korzystając po raz kolejny z Wniosku Uzupelnic con newton for integer| otrzymujemy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned H\!\left( x \right) &=&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ść

$\sum _{k=1}^n{k}^2=\left[x^n\right]H\left(x\right)=\frac{2n^3+3n+n}{6}.$

Przykład [Uzupelnij]

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

$A_k\left(x\right)=1+x^k+x^{2k}+x^{3k}+\dots ,$

dla $k=1,5,10,25$ i $50$. Z równości (Uzupelnic eq 1 przez 1-x|) 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 A\!\left( x \right)= A_1\!\left( x \right)&=& \frac{1}{1-x},\\ B\!\left( x \right)= A\!\left( x \right)\cdot A_5\!\left( x \right) &=&\frac{ A\!\left( x \right)}{1-x^5},\\ C\!\left( x \right)= B\!\left( x \right)\cdot A_{10}\!\left( x \right) &=&\frac{ B\!\left( x \right)}{1-x^{10}},\\ D\!\left( x \right)= C\!\left( x \right)\cdot A_{25}\!\left( x \right) &=&\frac{ C\!\left( x \right)}{1-x^{25}},\\ E\!\left( x \right)= D\!\left( x \right)\cdot A_{50}\!\left( x \right) &=&\frac{ D\!\left( x \right)}{1-x^{50}}, \endaligned}

skąd natychmiast:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned A\!\left( x \right)&=&1+x A\!\left( x \right),\\ B\!\left( x \right)&=& A\!\left( x \right)+x^5 B\!\left( x \right),\\ C\!\left( x \right)&=& B\!\left( x \right)+x^{10} C\!\left( x \right),\\ C\!\left( x \right)&=& D\!\left( x \right)+x^{25} C\!\left( x \right),\\ D\!\left( x \right)&=& E\!\left( x \right)+x^{50} D\!\left( x \right). \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ę:

{-2cm}

{

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

Przykład [Uzupelnij]

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\geq2. \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 $F\left(x\right)$ dla ciągu Fibonacci'ego

$F\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{f}_n{x}^n=x+\sum _{n=2}^{\mathrm{\infty }}(f_{n-1}+f_{n-2})x^n=1+x+xF\left(x\right)+x^{2}F\left(x\right).$

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

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

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 (Uzupelnic eq fib|) na sumę ułamków o mianownikach będących funkcjami liniowymi

$F\left(x\right)=\frac{x}{1-x-x^2}=\frac{x}{(1-\phi x)(1-\bar{\phi }x)}=\frac{1}{\sqrt{5}}(\frac{1}{(1-\phi x)}-\frac{1}{(1-\bar{\phi }x)}),$

gdzie $\phi =\frac{1+\sqrt{5}}{2}$ jest złotą liczbą oraz $\bar{\phi }=\frac{1-\sqrt{5}}{2}$ liczbą do niej sprzężoną. Korzystając z równania (Uzupelnic eq 1 przez 1-x|) otrzymujemy teraz

$F\left(x\right)=\frac{1}{\sqrt{5}}(\sum _{n=1}^{\mathrm{\infty }}{\phi }^n{x}^n-\sum _{n=1}^{\mathrm{\infty }}\stackrel{n}{\stackrel{‾}{\phi }}{x}^n)=\frac{1}{\sqrt{5}}\sum _{n=1}^{\mathrm{\infty }}({\phi }^n-\stackrel{n}{\stackrel{‾}{\phi }})x^n.$

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

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ć (błąd składni): {\displaystyle {\sf deg}\ P\!\left( x \right)=n} , jeśli $P\left(x\right)=p_0+p_{1}x+\dots +p_n{x}^n$.

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

Obserwacja [Uzupelnij]

Niech $A\left(x\right)$ oraz $B\left(x\right)$ będą wielomianami Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ A\!\left( x \right)\geq {\sf deg}\ B\!\left( x \right)} . Wtedy istnieją wielomiany $Q\left(x\right)$ oraz $R\left(x\right)$ takie, że

$A\left(x\right)=Q\left(x\right)B\left(x\right)+R\left(x\right),$

gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ R\!\left( x \right)<{\sf deg}\ A\!\left( x \right)={\sf deg}\ Q\!\left( x \right)+{\sf deg}\ B\!\left( x \right)} .

Przykład [Uzupelnij]

Niech

$A\left(x\right)=3x^5+5x^4+2x^3+x^2+2\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}B\left(x\right)=x^3+2x^2-1.$

Wtedy wielomiany

$Q\left(x\right)=3x^2-x+3\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}R\left(x\right)=x+2$

spełniają

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned A\!\left( x \right)&=&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\\ &=& Q\!\left( x \right) B\!\left( x \right)+ R\!\left( x \right). \endaligned}

Ponadto Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ A\!\left( x \right)=5=2+3={\sf deg}\ Q\!\left( x \right)+{\sf deg}\ B\!\left( x \right)} .

Wniosek [Uzupelnij]

Niech $P\left(x\right)$ oraz $Q\left(x\right)$ będą wielomianami takimi, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ P\!\left( x \right)\geq{\sf deg}\ Q\!\left( x \right)} . Wtedy funkcję wymierną $R\left(x\right)=P\left(x\right)/Q\left(x\right),$ można przedstawić w postaci

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

dla pewnych wielomianów $A\left(x\right)$ oraz $B\left(x\right)$ spełniających Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ B\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)} .

Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi $R\left(x\right)=P\left(x\right)/Q\left(x\right),$ dla których Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)} .

Twierdzenie [Uzupelnij]

Niech $P\left(x\right)$ oraz $Q\left(x\right)$ będą wielomianami takimi, że

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)} ,

• $Q\left(x\right)=S\left(x\right)T\left(x\right)$,

gdzie oba wielomiany $S\left(x\right),T\left(x\right)$ są stopnia co najmniej $2$,

• $q_0\ne 0$.

Wtedy istnieją wielomiany $A\left(x\right)$ oraz $B\left(x\right)$ takie, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ A\!\left( x \right)<{\sf deg}\ S\!\left( x \right)} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ B\!\left( x \right)<{\sf deg}\ T\!\left( x \right)} oraz

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

Uwaga [Uzupelnij]

Twierdzenie [[##thm PQ = AS BT|Uzupelnic thm PQ = AS BT|]] pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych.

Dowód [Uzupelnij]

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

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

gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)} , oraz $q_0\ne 0$. Załóżmy ponadto, że wielomian $Q\left(x\right)$ rozkłada się na następujący iloczyn czynników liniowych

$Q\left(x\right)=q_0{(1-{\rho }_{1}x)}^{m_1}\cdot {(1-{\rho }_{2}x)}^{m_2}\cdot \dots \cdot {(1-{\rho }_{k}x)}^{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 [[##thm PQ = AS BT|Uzupelnic thm PQ = AS BT|]] otrzymujemy wielomiany $P_1\left(x\right),\dots ,P_k\left(x\right)$ takie, że

$R\left(x\right)=\frac{P\left(x\right)}{Q\left(x\right)}=\frac{P_1\left(x\right)}{{(1-{\rho }_{1}x)}^{m_1}}+\frac{P_2\left(x\right)}{{(1-{\rho }_{2}x)}^{m_2}}+\dots +\frac{P_k\left(x\right)}{{(1-{\rho }_{k}x)}^{m_k}},$

gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ P_i\!\left( x \right)<m_i} . Na mocy Obserwacji Uzupelnic obs div| możemy sprowadzić wielomian $P_i\left(x\right)$ do

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned P_i\!\left( x \right)&=& P_i^1\!\left( x \right)\left( 1-\rho_ix \right)+\gamma_{m_i}\\ &=& P_i^2\!\left( x \right)\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ć (błąd składni): {\displaystyle m_i\geq{\sf deg}\ P_i\!\left( x \right)>{\sf deg}\ P_i^1\!\left( x \right)>{\sf deg}\ P_i^2\!\left( x \right)>\ldots} . W konsekwencji otrzymamy

$R\left(x\right)=\sum _{i=1}^k(\frac{{\gamma }_{i,1}}{1-{\rho }_{i}x}+\frac{{\gamma }_{i,2}}{{(1-{\rho }_{i}x)}^2}+\dots +\frac{{\gamma }_{i,m_i}}{{(1-{\rho }_{i}x)}^{m_i}}).$

Mnożąc teraz obie strony przez

$Q\left(x\right)/q_0={(1-{\rho }_{1}x)}^{m_1}\cdot {(1-{\rho }_{2}x)}^{m_2}\cdot \dots \cdot {(1-{\rho }_{k}x)}^{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 Uzupelnic con newton for integer| 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:

$[x^n]R\left(x\right)=\sum _{i=1}^k({\gamma }_{i,1}+{\gamma }_{i,2}(\genfrac{}{}{0ex}{}{n+1}{1})+\dots +{\gamma }_{i,m_i}(\genfrac{}{}{0ex}{}{n+m_i-1}{m_i})){\rho }_i^n.$

Przykład [Uzupelnij]

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

$R\left(x\right)=\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\left(x\right)=\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ń

$\{\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 R\!\left( x \right)&=&\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 $Q\left(x\right)$ funkcji wymiernej $R\left(x\right)=\frac{P\left(x\right)}{Q\left(x\right)}$ posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład $R\left(x\right)$ na sumę.

Twierdzenie [Uzupelnij]

Jeśli $R\left(x\right)=P\left(x\right)/Q\left(x\right)$, gdzie $Q\left(x\right)=q_0\cdot (1-{\rho }_{1}x)\cdot \dots \cdot (1-{\rho }_{1}x)$ i liczby ${\rho }_1,\dots ,{\rho }_l$ są parami różne, to w przypadku gdy $P\left(x\right)$ jest wielomianem stopnia mniejszego niż $l$, zachodzi

$\left[x^n\right]R\left(x\right)=a_1{\rho }_1^n+\dots +a_l{\rho }_l^n,\text{<mrow data-mjx-texclass="ORD">dla</mrow>}{a}_k=\frac{-{\rho }_k\cdot P(1/{\rho }_k)}{Q^{\prime }(1/{\rho }_k)}.$

Przykład [Uzupelnij]

Mianownik $Q\left(x\right)$ funkcji wymiernej

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

ma trzy różne pierwiastki i można $R\left(x\right)$ przedstawić jako

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

Na mocy twierdzenia Uzupelnic thm wymierne| otrzymujemy więc, że

$\left[x^n\right]R\left(x\right)=-\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 rekurencyjne to równanie postaci

$\{\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}+\dots +a_k{r}_{n-k}\text{<mrow data-mjx-texclass="ORD">dla</mrow>}n\ge k,\end{array}$

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

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

$\{\begin{array}{rcl}{r}_0& =& c_0,\\ r_1& =& c_1,\\ r_n& =& a_1{r}_{n-1}+a_2{r}_{n-2}\text{<mrow data-mjx-texclass="ORD">dla</mrow>}n\ge 2.\end{array}$

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned R\!\left( x \right)&=&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 R\!\left( x \right)+a_2x^2 R\!\left( x \right), \endaligned}

tak więc

$R\left(x\right)=\frac{c_0+(c_1-a_1{c}_0)x}{1-a_{1}x-a_2{x}^2}$

Dla funkcji $A\left(x\right)=1-a_{1}x-a_2{x}^2=(1-{\rho }_{1}x)(1-{\rho }_{2}x)$ mogą zajść trzy przypadki:

• ${\rho }_1\ne {\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.

• $▽$

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\left(x\right)=\frac{P\left(x\right)}{1-a_{1}x-a_2{x}^2-\dots -a_k{x}^k},$

gdzie $P\left(x\right)$ jest wielomianem co najwyżej stopnia $k-1$, zależnym od wartości $c_0,\dots ,c_{k-1},a_1,\dots ,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\left(x\right)$ zgodnie z równaniem (Uzupelnic eq R(x)|).

Przykład [Uzupelnij]

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

$\{\begin{array}{rcl}{r}_0& =& 0,\\ r_1& =& 0,\\ r_2& =& 1,\\ r_n& =& r_{n-1}+r_{n-2}-r_{n-3}\text{<mrow data-mjx-texclass="ORD">dla</mrow>}n\ge 3.\end{array}$

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

$R\left(x\right)=x^2+xR\left(x\right)+x^{2}R\left(x\right)-x^{3}R\left(x\right).$

Po dokonaniu prostego wyliczenia dostajemy:

$R\left(x\right)=\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\left(x\right)$, a zatem mamy:

$r_n=-\frac{1}{4}+\frac{1}{2}(n+1)-\frac{1}{4}{(-1)}^n\text{<mrow data-mjx-texclass="ORD">dladowolnego</mrow>}n=0,1,2,3,\dots .$