Test Arka: Różnice pomiędzy wersjami

Wersja z 13:05, 21 sie 2006

Problemy ze wzorami na osiłku

$M$ $M^{'}$ $M^{'}$ 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}

{

0mm

#1 10mm }{{ $◻$ }

}

{article} {../makraB}

0mm

Uzupelnij tytul
Funkcje tworzące

10mm

0mm

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

A_{1} = [0] + (1) + (1) (1) + (1) (1) (1) + (1) (1) (1) (1) + \dots

i analogicznie przeanalizujmy sumę dla pieciocentówek

A_{5} = [0] + (5) + (5) (5) + (5) (5) (5) + (5) (5) (5) (5) + \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 „\alignedB”): {\displaystyle \alignedB= 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 $(10)$ , ćwierćdolarówek $(25)$ , oraz półdolarówek $(50)$ wyglądają następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\alignedA”): {\displaystyle \alignedA_{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 $(10)$ , $(25)$ , i na końcu $(50)$ do możliwych rozmian uzyskujemy odpowiednio:

Parser nie mógł rozpoznać (nieznana funkcja „\alignedC”): {\displaystyle \alignedC&=&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 & = & ((1)) + ((1) (1)) + ((1) (1) (1)) + ((1) (1) (1) (1)) \\ + ((1) (1) (1) (1) (1) + (5)) \\ + ((1) (1) (1) (1) (1) (1) + (5) (1)) + \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 $(1)$ , $(5)$ , $(10)$ , $(25)$ , oraz $(50)$ . Pomysłem pochodzącym od Pólya, było zastąpienie monety $(1)$ przez zmienną $x$ , monety $(5)$ przez $x \cdot x \cdot x \cdot x \cdot x = x^{5}$ i analogicznie $(10)$ przez $x^{10}$ , $(25)$ przez $x^{25}$ , oraz $(50)$ przez $x^{50}$ . Uzyskujemy w ten sposób nieskończony szereg zmiennej $x$ :

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

0mm

Funkcja tworząca $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

G (x) = \sum_{n = 0}^{\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 (x)$ używać będziemy oznaczenia $[x^{n}] G (x) = g_{n}$ .

10mm

Uwaga [Uzupelnij]

Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie $G (x)$ jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu $G (x) = \sum_{n = 0}^{\infty} g_{n} x^{n}$ . Z wykładu Analiza Matematyczna wiemy, że szereg $G (x)$ jest zbieżny wtedy i tylko wtedy, gdy istnieje stała $M \geq 0$ ograniczająca wszystkie skończone początkowe sumy, tzn.

| g_{0} | + | g_{1} x | + | g_{2} x^{2} | + \dots + | g_{n} x^{n} | \leq M

zachodzi dla dowolnego $n \geq 0$ . Ponadto jeśli dla pewnej liczby $x_{0} \in ℝ$ szereg $G (x_{0}) = g_{0} + g_{1} x_{0} + g_{2} x_{0}^{2} + \dots$ jest zbieżny, to i także szereg $G (x_{1}) = g_{0} + g_{1} x_{1} + g_{2} x_{1}^{2} + \dots$ jest zbieżny dla dowolnego $x_{1} \in ℝ$ spełniającego $| x_{1} | \leq | x_{0} |$ . Możemy więc określić promień zbieżności szeregu jako taką liczbę $r \in ℝ_{*} \cup {\infty} = [0, + \infty]$ , że

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

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

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

G : (- r, r) ⟶ ℝ,

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

Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg $G (x) = 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 (x) = 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.

Dla dwu funkcji tworzących $F (x) = f_{0} + f_{1} x + f_{2} x^{2} + \dots$ oraz $G (x) = g_{0} + g_{1} x + g_{2} x^{2} + \dots$ mamy:

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

Twierdzenie [Uzupelnij]

Funkcja tworząca postaci

G (x) = 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 (x)$ taka, że $U (x) 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.

Dla dwu funkcji tworzących $F (x) = f_{0} + f_{1} x + f_{2} x^{2} + \dots$ oraz $G (x) = g_{0} + g_{1} x + g_{2} x^{2} + \dots$ mamy:

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

Uzupelnij tytul
Funkcje tworzące w zliczaniu

Widzieliśmy już, że dla $n \in ℕ$

{(1 + x)}^{m} = (\binom{m}{0}) x^{0} + (\binom{m}{1}) x + (\binom{m}{2}) x^{2} + \dots + (\binom{m}{m - 1}) x^{m - 1} + (\binom{m}{m}) x^{m} = \sum_{n = 0}^{\infty} (\binom{m}{n}) x^{n} .

Przyjrzyjmy się teraz rozwinięciu w szereg funkcji ${(1 + x)}^{y}$ , gdzie $y \in ℝ$ 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ę.

0mm

Uogólniony symbol dwumianowy $(\binom{y}{n})$ , gdzie $y \in ℝ$ oraz $n \in ℕ$ 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}. }

10mm

Uwaga [Uzupelnij]

Oczywiście dla $y \in ℕ$ spełniającego dodatkowo $y \geq n$ , uogólniony symbol dwumianowy $(\binom{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}^{\infty} (\binom{y}{n}) x^{n} .

Dla liczby naturalnej $m$ zachodzi

\frac{1}{{(1 - x)}^{m + 1}} = \sum_{n = 0}^{\infty} (\binom{m + n}{n}) x^{n} .

Dowód [Uzupelnij]

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

0mm

Przykład.

Policzmy sumę

\sum_{k = 0}^{n} k^{2} = 1 + 4 + 9 + \dots + n^{2} .

Zacznijmy od znalezienia zwartej postaci funkcji tworzącej $G (x) = \sum_{n = 0}^{\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}^{\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}^{\infty} (\binom{n + 2}{n}) x^{n} = \frac{1}{2} \sum_{n = 0}^{\infty} n^{2} x^{n} + \frac{3}{2} \sum_{n = 0}^{\infty} n x^{n} + \sum_{n = 0}^{\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 (x)$ dla ciągu $1, 4, 9, \dots, n^{2}, \dots$ :

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

H (x) = \frac{G (x)}{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 „\alignedH”): {\displaystyle \alignedH\!\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} = [x^{n}] H (x) = \frac{2 n^{3} + 3 n + n}{6} .

0mm

Przykład.

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

A_{k} (x) = 1 + x^{k} + x^{2 k} + x^{3 k} + \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^{2 k} + x^{3 k} + \dots, = \frac{1}{1 - x^{k}}

tak więc:

Parser nie mógł rozpoznać (nieznana funkcja „\alignedA”): {\displaystyle \alignedA\!\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 „\alignedA”): {\displaystyle \alignedA\!\left( x \right)&=&1+xA\!\left( x \right),\\ B\!\left( x \right)&=&A\!\left( x \right)+x^5B\!\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}

Uzupelnij tytul
$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.

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

0mm

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 „\alignedf”): {\displaystyle \alignedf_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 (x)$ dla ciągu Fibonacci'ego

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

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

F (x) = \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 (x) = \frac{x}{1 - x - x^{2}} = \frac{x}{(1 - φ x) (1 - \overline{φ} x)} = \frac{1}{\sqrt{5}} (\frac{1}{(1 - φ x)} - \frac{1}{(1 - \overline{φ} x)}),

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

F (x) = \frac{1}{\sqrt{5}} (\sum_{n = 1}^{\infty} φ^{n} x^{n} - \sum_{n = 1}^{\infty} \overset{n}{\overline{φ}} x^{n}) = \frac{1}{\sqrt{5}} \sum_{n = 1}^{\infty} (φ^{n} - \overset{n}{\overline{φ}}) x^{n} .

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

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.

0mm

Stopień wielomianu Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ P\!\left( x \right)=n} , jeśli $P (x) = p_{0} + p_{1} x + \dots + p_{n} x^{n}$ .

10mm

0mm

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

10mm

Niech $A (x)$ oraz $B (x)$ 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 (x)$ oraz $R (x)$ takie, że

A (x) = Q (x) B (x) + R (x),

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)} .

0mm

Przykład.

Niech

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

Wtedy wielomiany

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

spełniają

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

Niech $P (x)$ oraz $Q (x)$ 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 (x) = P (x) / Q (x),$ można przedstawić w postaci

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

dla pewnych wielomianów $A (x)$ oraz $B (x)$ spełniających 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 (x) = P (x) / Q (x),$ 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 (x)$ oraz $Q (x)$ 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 (x) = S (x) T (x)$ ,

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

$q_{0} \neq 0$ .

Wtedy istnieją wielomiany $A (x)$ oraz $B (x)$ 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 (x)}{Q (x)} = \frac{A (x)}{S (x)} + \frac{B (x)}{T (x)} .

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 (x) = \frac{P (x)}{Q (x)},

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} \neq 0$ . Załóżmy ponadto, że wielomian $Q (x)$ rozkłada się na następujący iloczyn czynników liniowych

Q (x) = q_{0} {(1 - ρ_{1} x)}^{m_{1}} \cdot {(1 - ρ_{2} x)}^{m_{2}} \cdot \dots \cdot {(1 - ρ_{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} (x), \dots, P_{k} (x)$ takie, że

R (x) = \frac{P (x)}{Q (x)} = \frac{P_{1} (x)}{{(1 - ρ_{1} x)}^{m_{1}}} + \frac{P_{2} (x)}{{(1 - ρ_{2} x)}^{m_{2}}} + \dots + \frac{P_{k} (x)}{{(1 - ρ_{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} (x)$ do

Parser nie mógł rozpoznać (nieznana funkcja „\alignedP”): {\displaystyle \alignedP_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 (x) = \sum_{i = 1}^{k} (\frac{γ_{i, 1}}{1 - ρ_{i} x} + \frac{γ_{i, 2}}{{(1 - ρ_{i} x)}^{2}} + \dots + \frac{γ_{i, m_{i}}}{{(1 - ρ_{i} x)}^{m_{i}}}) .

Mnożąc teraz obie strony przez

Q (x) / q_{0} = {(1 - ρ_{1} x)}^{m_{1}} \cdot {(1 - ρ_{2} x)}^{m_{2}} \cdot \dots \cdot {(1 - ρ_{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 $γ_{i, j}$ . Z drugiej strony, z wniosku Uzupelnic con newton for integer| wynika, że

\frac{1}{{(1 - ρ x)}^{m + 1}} = \sum_{n = 1}^{\infty} (\binom{m + n}{m}) ρ^{n} x^{n}

i w konsekwencji:

[x^{n}] R (x) = \sum_{i = 1}^{k} (γ_{i, 1} + γ_{i, 2} (\binom{n + 1}{1}) + \dots + γ_{i, m_{i}} (\binom{n + m_{i} - 1}{m_{i}})) ρ_{i}^{n} .

0mm

Przykład.

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

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

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

R (x) = \frac{x^{2}}{{(1 - x)}^{2} \cdot (1 + x)} = \frac{α}{1 - x} + \frac{β}{{(1 - x)}^{2}} + \frac{γ}{1 + x} .

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

x^{2} = α (1 - x^{2}) + β (1 + x) + γ (1 - 2 x + x^{2}) .

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

{\begin{array}{rrrcl} α & + β & + γ & = & 0 \\ α & - 2 γ & = & 0 \\ - β & + γ & = & 1 . \end{array}

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

Parser nie mógł rozpoznać (nieznana funkcja „\alignedR”): {\displaystyle \alignedR\!\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 (x)$ funkcji wymiernej $R (x) = \frac{P (x)}{Q (x)}$ posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład $R (x)$ na sumę.

Twierdzenie [Uzupelnij]

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

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

0mm

Przykład.

Mianownik $Q (x)$ funkcji wymiernej

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

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

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

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

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

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

0mm

Jednorodne, liniowe równanie rekurencyjne to równanie postaci

{\begin{array}{rcl} r_{0} & = & c_{0}, \\ \dots \\ r_{k - 1} & = & c_{k - 1}, \\ r_{n} & = & a_{1} r_{n - 1} + a_{2} r_{n - 2} + \dots + a_{k} r_{n - k} dla n \geq k, \end{array}

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

10mm

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} dla n \geq 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 „\alignedR”): {\displaystyle \alignedR\!\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_1xR\!\left( x \right)+a_2x^2R\!\left( x \right), \endaligned}

tak więc

R (x) = \frac{c_{0} + (c_{1} - a_{1} c_{0}) x}{1 - a_{1} x - a_{2} x^{2}}

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

$ρ_{1} \neq ρ_{2}$ są różnymi liczbami rzeczywistymi. Wtedy

r_{n} = α ρ_{1}^{n} + β ρ_{2}^{n},

gdzie $α$ oraz $β$ są liczbami rzeczywistymi.

$ρ_{1} = ρ_{2}$ . Wtedy

r_{n} = (α n + β) ρ_{1}^{n},

gdzie $α$ oraz $β$ są liczbami rzeczywistymi.

$▽$

Wartości $ρ_{1}$ oraz $ρ_{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} = α ρ_{1}^{n} + β ρ_{2}^{n} .

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

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

R (x) = \frac{P (x)}{1 - a_{1} x - a_{2} x^{2} - \dots - a_{k} x^{k}},

gdzie $P (x)$ 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 (x)$ zgodnie z równaniem (Uzupelnic eq R(x)|).

0mm

Przykład.

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} dla n \geq 3 . \end{array}

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

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

Po dokonaniu prostego wyliczenia dostajemy:

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

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

r_{n} = - \frac{1}{4} + \frac{1}{2} (n + 1) - \frac{1}{4} {(- 1)}^{n} dladowolnego n = 0, 1, 2, 3, \dots .

Test Arka: Różnice pomiędzy wersjami

Wersja z 13:05, 21 sie 2006

Problemy ze wzorami na osiłku

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 15: / Linia 15: @@
 <hr>
-{}
+{thm}{Twierdzenie}
+{obs}[thm]{Obserwacja}
+{con}[thm]{Wniosek}
-{}
+{
-==Ciągi liczbowe. Ćwiczenia==
+mm
-{{cwiczenie|[Uzupelnij]||
+'''#1'''
+mm }{{<math>\square</math>}
-Obliczyć następujące granice ciągów:<br>
+}
-'''(1)'''
-<math>\displaystyle
+{article}
-\lim\limits_{n\rightarrow +\infty}\frac{2n^2+1}{3n^2-1}</math><br>
+{../makraB}
-'''(2)'''
-<math>\displaystyle
+mm
-\lim\limits_{n\rightarrow +\infty}\frac{2n^2+n+2}{n\sqrt{n}}</math><br>
-'''(3)'''
+{| border=1
-<math>\displaystyle
+|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
-\lim\limits_{n\rightarrow +\infty}\frac{-n+1}{n^2+2}.</math>
+|-
-}}
+| '''Funkcje tworzące'''
+|-
+|
+|}
+mm
+mm
+'''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 <math>\left( 1 \right)</math>,
+pięciocentówek <math>\left( 5 \right)</math>,
+dziesięciocentówek <math>\left( 10 \right)</math>,
+ćwierćdolarówek <math>\left( 25 \right)</math>,
+oraz półdolarówki <math>\left( 50 \right)</math>.
+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ę <math>\left[0\right]</math>, 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
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
+<center><math>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)+\ldots
-'''(1)''' Podzielić licznik i mianownik przez <math>n^2</math>
+</math></center>
-i skorzystać z twierdzeń o arytmetyce granic.<br>
-'''(2)''' Wykorzystać twierdzenie o dwóch ciągach.<br>
-'''(3)''' Sposób I. Wykorzystać twierdzenie o trzech ciągach.<br>
-Sposób II.
-Podzielić licznik i mianownik przez <math>n^2</math>
-oraz skorzystać z twierdzeń o arytmetyce granic.
-{}<math>\Box</math></div></div>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+i analogicznie przeanalizujmy sumę dla pieciocentówek
-'''(1)'''
-Dzielimy licznik i mianownik przez <math>n^2</math> i dostajemy:
-<center><math>\lim\limits_{n\rightarrow +\infty}\frac{2n^2+1}{3n^2-1}
+<center><math>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)+\ldots
-\ =\
-\lim\limits_{n\rightarrow +\infty}
-\frac{\displaystyle 2+\overbrace{\frac{1}{n^2}}^{\rightarrow 0}}{\displaystyle 3-\underbrace{\frac{1}{n^2}}_{\rightarrow 0}}
-\ =\
-\frac{2}{3},
 </math></center>
-przy czym w ostatniej równości wykorzystujemy twierdzenia o
+Wtedy zbiór par  <math>A_1 \times A_5</math>
-arytmetyce granic (dla sumy i iloczynu; patrz Twierdzenie [[##t.new.am1.w.04.080|Uzupelnic t.new.am1.w.04.080|]])
+jest zbiorem wszystkich możliwości rozmiany kwoty mając do dyspozycji
-oraz fakt, że
+dowolnie wiele jednocentówek oraz pięciocentówek.
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} \frac{1}{n^2}=0</math>
-(patrz Przykład [[##p.new.am1.w.03.210|Uzupelnic p.new.am1.w.03.210|]] i Twierdzenie
+<center><math>\alignedB= A_1 \times A_5
-[[##t.new.am1.w.04.080|Uzupelnic t.new.am1.w.04.080|]]).<br>
+&=&\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)\\
-<br>
+&&\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)\\
-'''(2)'''
+&=&\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
-Zauważmy, że
+\endaligned</math></center>
+Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek <math>\left( 10 \right)</math>,
+ćwierćdolarówek <math>\left( 25 \right)</math>,
+oraz półdolarówek <math>\left( 50 \right)</math> wyglądają następująco:
+<center><math>\alignedA_{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</math></center>
-<center><math>\begin{array} {ccccc}
+Dodając kolejno  monety <math>\left( 10 \right)</math>, <math>\left( 25 \right)</math>,
-\displaystyle\frac{2n^2}{n\sqrt{n}}     & \le & \displaystyle\frac{2n^2+n+2}{n\sqrt{n}}\\
+i na końcu <math>\left( 50 \right)</math>
-\shortparallel                          &     &                           \\
+do możliwych rozmian uzyskujemy odpowiednio:
-\displaystyle 2\sqrt{n}                 &     &                           \\
-\downarrow                              &     &                           \\
+<center><math>\alignedC&=&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)\\
-+\infty                                 &     &
+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</math></center>
+Grupując teraz składniki sumy <math>E</math> w podsumy o tych samych wartościach
+dostajemy wyrażenie:
+<center><math>\begin{array} {rcl}
+E&=&\big(\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\big)\\
+&&+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 5 \right)\big)\\
+&&+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 5 \right)\left( 1 \right)\big)+\ldots
 \end{array}
 </math></center>
-(przy czym ostatnią zbieżność <math>\displaystyle\lim\limits_{n\rightarrow +\infty} \sqrt{n}=+\infty</math>
+Zliczając zaś tylko składniki w podsumie odpowiadającej  wartości <math>n</math> centów,
-łatwo pokazać z definicji granicy niewłaściwej).
+otrzymujemy liczbę sposobów, na które można rozmienić <math>n</math> centów przy użyciu monet
-Zatem korzystając z twierdzenia o dwóch ciągach
+<math>\left( 1 \right)</math>, <math>\left( 5 \right)</math>, <math>\left( 10 \right)</math>, <math>\left( 25 \right)</math>, oraz <math>\left( 50 \right)</math>.
-(patrz Twierdzenie [[##t.new.am1.w.04.120|Uzupelnic t.new.am1.w.04.120|]](a))
+Pomysłem pochodzącym od Pólya, było zastąpienie
-wnioskujemy, że
+monety <math>\left( 1 \right)</math> przez zmienną <math>x</math>,
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} \frac{2n^2+n+2}{n\sqrt{n}}=+\infty</math><br>
+monety <math>\left( 5 \right)</math> przez <math>x\cdot x\cdot x\cdot x\cdot x=x^5</math>
-'''(3)'''
+i analogicznie <math>\left( 10 \right)</math> przez <math>x^{10}</math>,
-'''Sposób I.'''
+<math>\left( 25 \right)</math> przez <math>x^{25}</math>,
-Zauważmy, że
+oraz <math>\left( 50 \right)</math> przez <math>x^{50}</math>.
+Uzyskujemy w ten sposób nieskończony szereg zmiennej <math>x</math>:
+<center><math>\alignedE\!\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</math></center>
+Godne zauważenia jest, że liczba różnych możliwych sposobów rozmiany <math>n</math> centów
+(równa liczbie grup monet w odpowiednim nawiasie we wzorze ([[##int wzor S|Uzupelnic int wzor S|]]))
+jest równa współczynnikowi stojącemu przy jednomianie <math>x^n</math>.
+mm
+'''Funkcja tworząca''' <math>G\!\left( x \right)</math> dla ciągu liczb rzeczywistych
+(lub zespolonych) <math>\left( g_0,g_1,g_2,g_3,\ldots \right)</math>
+to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) <math>x</math> postaci
+<center><math>G\!\left( x \right)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots.
+</math></center>
+Na oznaczenie współczynnika <math>n</math>-tego wyrazu szeregu <math>G\!\left( x \right)</math>
+używać będziemy  oznaczenia  <math>\left[x^n\right]G\!\left( x \right)=g_n</math>.
-<center><math>\begin{array} {ccccc}
+mm
-\displaystyle -\frac{n}{n^2} & \le & \displaystyle\frac{-n+1}{n^2+2} & \le & 0\\
-\shortparallel               &     &                                 &     & \downarrow\\
+{{uwaga|[Uzupelnij]||
-\displaystyle -\frac{1}{n}   &     &                                 &     & 0\\
-\downarrow                   &     &                                 &     & \\
+Na funkcje tworzące można spojrzeć dwoiście.
-                            &     &                                 &     & \\
+Pierwszym sposobem jest potraktowanie <math>G\!\left( x \right)</math> jako szeregu liczb rzeczywistych
-\end{array}
+(lub ogólniej zespolonych).
+Oczywistym pytaniem jest tu kwestia zbieżności szeregu
+<math>G\!\left( x \right)=\sum_{n=0}^{\infty}{g_nx^n}</math>.
+Z wykładu Analiza Matematyczna wiemy,
+że szereg <math>G\!\left( x \right)</math> jest zbieżny wtedy i tylko wtedy,
+gdy istnieje stała <math>M\geq0</math> ograniczająca wszystkie skończone początkowe sumy, tzn.
+<center><math>\left\vert g_0 \right\vert+\left\vert g_1x \right\vert+\left\vert g_2x^2 \right\vert+\ldots+\left\vert g_nx^n \right\vert\leq M
 </math></center>
-Zatem korzystając z twierdzenia a trzech ciągach wnioskujemy,
+zachodzi dla dowolnego <math>n\geq0</math>.
-że
+Ponadto jeśli dla pewnej liczby <math>x_0\in\mathbb{R}</math>
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} \frac{-n+1}{n^2+2}=0.</math><br>
+szereg <math>G\!\left( x_0 \right)=g_0+g_1x_0+g_2x_0^2+\ldots</math> jest zbieżny,
-'''Sposób II.'''
+to i także szereg <math>G\!\left( x_1 \right)=g_0+g_1x_1+g_2x_1^2+\ldots</math>
-Dzieląc licznik i mianownik przez <math>n^2</math>
+jest zbieżny dla dowolnego <math>x_1\in\mathbb{R}</math> spełniającego <math>\left\vert x_1 \right\vert\leq\left\vert x_0 \right\vert</math>.
-oraz korzystając z twierdzeń o arytmetyce granic, mamy
+Możemy więc określić  ''promień zbieżności'' szeregu
+jako taką liczbę <math>r\in\mathbb{R}_*\cup\left\lbrace \infty \right\rbrace=\left[0,+\infty\right]</math>, że
+* jeśli <math>x<r</math>, to  <math>G\!\left( x \right)</math> jest zbieżny;
+* jeśli <math>x>r</math>, to  <math>G\!\left( x \right)</math> jest rozbieżny.
-<center><math>\lim\limits_{n\rightarrow +\infty} \frac{-n+1}{n^2+2}
+Szereg <math>G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> można więc potraktować jako funkcję
-\ =\
-\lim\limits_{n\rightarrow +\infty}\frac{\displaystyle \overbrace{-\frac{1}{n}}^{\rightarrow 0}+\overbrace{\frac{1}{n^2}}^{\rightarrow 0}}{\displaystyle 1+\underbrace{\frac{2}{n^2}}_{\rightarrow 0}}
+<center><math>G:\left( -r,r \right)\longrightarrow\mathbb{R},
-\ =\
-.
 </math></center>
-{}<math>\Box</math></div></div>
+o wartościach
+<math>G\!\left( x \right)=\lim_{n\rightarrow\infty}{\left( g_0+g_1x+g_2x^2+\ldots+g_nx^n \right)}.
+</math>
+Oczywiście <math>G\!\left( 0 \right)=g_0</math>, więc dla <math>x=0</math> szereg <math>G\!\left( x \right)</math> jest zbieżny.
+Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach
+jest spojrzenie na szereg <math>G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math>
+jako formę zapisu ciągu <math>\left( g_0,g_1,g_2,\ldots \right)</math>,
+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.
-{{cwiczenie|[Uzupelnij]||
+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 <math>G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math>
+jest funkcją tworzącą ciągu <math>\left( g_0,g_1,g_2,g_3,\ldots \right)</math>,
+oraz w jakiś sposób będziemy w stanie poznać postać zwartą funkcji <math>G(x)</math>,
+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.
-Obliczyć następujące granice ciągów:<br>
+Będziemy się zajmowali jedynie tymi funkcjami, dla których promień zbieżności <math>r>0</math>.
-'''(1)'''
+Ponadto będziemy pomijać problem zbieżności oraz wartość <math>r</math> promienia zbieżności,
-<math>\displaystyle
+skupiając się jedynie na przekształceniach wzorów.
-\lim\limits_{n\rightarrow +\infty} \frac{\binom{n+2}{n}}{n^2}</math><br>
+Poniżej zebrane zostały te własności,
-'''(2)'''
+które często wykorzystywane są w takich przekształceniach.
-<math>\displaystyle
-\lim\limits_{n\rightarrow +\infty} \frac{\binom{n+3}{n}}{n^3}.</math>
 }}
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
+Dla dwu funkcji tworzących <math>F\!\left( x \right)=f_0+f_1x+f_2x^2+\ldots</math>
-'''(1)''' Rozpisać symbol Newtona. Podzielić licznik i mianownik przez <math>n^2.</math><br>
+oraz  <math>G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
-'''(2)''' Rozwiązać analogicznie do przykładu (1).
-{}<math>\Box</math></div></div>
+<center><math>\alignedF\!\left( x \right)=G\!\left( x \right)&\Leftrightarrow& f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots\\
+&&\\
+\alpha\cdotF\!\left( x \right)+\beta\cdotG\!\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)\cdotG\!\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</math></center>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+Wyrażenie <math>F\!\left( x \right)\cdotG\!\left( x \right)</math> nazywać będziemy splotem szeregów <math>F\!\left( x \right)</math> oraz <math>G\!\left( x \right)</math>.
-'''(1)'''
-Rozpiszmy symbol Newtona występujący w wyrazach ciągu
-<center><math>\binom{n+2}{n}
+{{twierdzenie|[Uzupelnij]||
-\ =\
-\frac{(n+2)!}{n!\cdot 2!}
+Funkcja tworząca postaci
-\ =\
-\frac{(n+1)(n+2)}{2}
+<center><math>G\!\left( x \right)=g_0+g_1x+g_2x^2+g_3x^3+\ldots
 </math></center>
-Zatem liczymy:
+ma odwrotną względem mnożenia (splotu),
+tzn. istnieje funkcja tworząca <math>U\!\left( x \right)</math> taka,
+że <math>U\!\left( x \right)G\!\left( x \right)=1</math>,
+wtedy i tylko wtedy, gdy <math>g_0\neq0</math>.
+}}
-<center><math>\aligned
+Następne własności są bardzo pomocne w dokonywanych przekształceniach
-\displaystyle
+funkcji tworzących.
-\lim\limits_{n\rightarrow +\infty} \frac{\binom{n+2}{n}}{n^2}
-& = &
+Dla dwu funkcji tworzących <math>F\!\left( x \right)=f_0+f_1x+f_2x^2+\ldots</math>
-\displaystyle
+oraz  <math>G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
-\lim\limits_{n\rightarrow +\infty} \frac{(n+1)(n+2)}{2n^2}
-\ =\
+<center><math>\alignedx^mG\!\left( x \right)&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots\\
-\lim\limits_{n\rightarrow +\infty}\frac{n^2+3n+2}{2n^2}\\
+\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\\
-\displaystyle
+G'\!\left( x \right)&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots\\
-\lim\limits_{n\rightarrow +\infty}\frac{1}{2}
+\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\\
-+\underbrace{\lim\limits_{n\rightarrow +\infty}\frac{3}{2}\cdot\frac{1}{n}}_{=0}
+\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
-+\underbrace{\lim\limits_{n\rightarrow +\infty}\frac{1}{n^2}}_{=0}
-\ =\
-\frac{1}{2}.
 \endaligned</math></center>
-'''(2)'''
+{| border=1
-Rozpiszmy symbol Newtona występujący w wyrazach ciągu
+|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
+|-
+| '''Funkcje tworzące w zliczaniu'''
+|-
+|
+|}
+Widzieliśmy już, że dla <math>n\in \mathbb{N}</math>
+<center><math>\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}^\infty {m \choose n}x^n.
+</math></center>
+Przyjrzyjmy się teraz rozwinięciu w szereg funkcji <math>\left( 1+x \right)^y</math>,
+gdzie <math>y\in\mathbb{R}</math> 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ę.
+mm
+'''Uogólniony symbol dwumianowy''' <math>{ y \choose n }</math>, gdzie <math>y\in\mathbb{R}</math> oraz <math>n\in\mathbb{N}</math> jest oznaczeniem na
+<center><math>{ 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}.
+</math></center>
+mm
+{{uwaga|[Uzupelnij]||
+Oczywiście dla <math>y\in\mathbb{N}</math> spełniającego dodatkowo <math>y\geq n</math>,
+uogólniony symbol dwumianowy <math>{ y \choose n }</math>
+jest liczbą <math>n</math>-elementowych podzbiorów zbioru <math>y</math>-elementowego.
+}}
+{{twierdzenie|[Uzupelnij]||
+Dla liczby rzeczywistej <math>y</math> oraz liczby naturalnej <math>n</math> zachodzi
-<center><math>\binom{n+3}{n}
+<center><math>\left( 1+x \right)^y=\sum_{n=0}^{\infty}{ y \choose n }x^n.
-\ =\
-\frac{(n+3)!}{n!\cdot 3!}
-\ =\
-\frac{(n+1)(n+2)(n+3)}{6}
 </math></center>
-Zatem liczymy:
+}}
-<center><math>\aligned
+Dla liczby naturalnej <math>m</math> zachodzi
-\displaystyle
-\lim\limits_{n\rightarrow +\infty} \frac{\binom{n+3}{n}}{n^3}
-& = &
-\displaystyle
-\lim\limits_{n\rightarrow +\infty} \frac{(n+1)(n+2)(n+3)}{6n^3}
-\ =\
-\lim\limits_{n\rightarrow +\infty}\frac{n^3+6n^2+11n+6}{6n^3}\\
-& = &
-\displaystyle
-\lim\limits_{n\rightarrow +\infty}\frac{1}{6}
-+\underbrace{\lim\limits_{n\rightarrow +\infty}\frac{1}{n}}_{=0}
-+\underbrace{\lim\limits_{n\rightarrow +\infty}\frac{11}{6}\cdot\frac{1}{n^2}}_{=0}
-+\underbrace{\lim\limits_{n\rightarrow +\infty}\frac{1}{n^3}}_{=0}
-\ =\
-\frac{1}{6}.
-\endaligned</math></center>
-{}<math>\Box</math></div></div>
+<center><math>\frac{1}{\left( 1-x \right)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.
+</math></center>
-{{cwiczenie|[Uzupelnij]||
+{{dowod|[Uzupelnij]||
-Obliczyć następujące granice ciągów:<br>
+Dowód zostawiony jest jako ćwiczenie '''[ex][ex newton for integer]'''.
-'''(1)'''
-<math>\displaystyle
-\lim\limits_{n\rightarrow +\infty}\frac{5^{n+1}+1+6^{n+1}}{3\cdot 6^n}</math><br>
-'''(2)'''
-<math>\displaystyle
-\lim\limits_{n\rightarrow +\infty}\frac{2^{n+1}+3^n}{3^{2n}+2}</math><br>
-'''(3)'''
-<math>\displaystyle
-\lim\limits_{n\rightarrow +\infty}\frac{1+\frac{1}{4}+\frac{1}{16}+\ldots+\frac{1}{4^n}}{1+\frac{1}{3}+\frac{1}{9}+\ldots+\frac{1}{3^n}}.</math>
 }}
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
+mm
-'''(1)''' Wykonać dzielenie <math>6^n.</math><br>
-'''(2)''' Sposób I. Wykorzystać twierdzenie o trzech ciągach.<br>
+'''Przykład. '''
-Sposób II.
-Podzielić licznik i mianownik przez <math>3^{2n}</math>
+Policzmy sumę
-i skorzystać z twierdzeń o arytmetyce granic.<br>
-'''(3)''' Wykorzystać wzór na sumę skończonego
+<center><math>\sum_{k=0}^nk^2=1+4+9+\ldots+n^2.
-ciągu geometrycznego (patrz Uwaga [[##u.1.0100|Uzupelnic u.1.0100|]]).
+</math></center>
-{}<math>\Box</math></div></div>
+Zacznijmy od znalezienia zwartej postaci funkcji tworzącej
+<math>G\!\left( x \right)=\sum_{n=0}^{\infty}n^2x^n</math>.
+Korzystając z Wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy:
+<center><math>\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</math></center>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+Po przekształceniu równości ([[##eq 11|Uzupelnic eq 11|]]) uzyskuje się
-'''(1)'''
-Wykonując dzielenie przez <math>6^n</math> dostajemy:
-<center><math>\lim\limits_{n\rightarrow +\infty}\frac{5^{n+1}+1+6^{n+1}}{3\cdot 6^n}
+<center><math>
-\ =\
+\sum_{n=0}^{\infty}nx^n= \frac{1}{\left( 1-x \right)^2}
-\lim\limits_{n\rightarrow +\infty}\frac{5}{3}\bigg(\frac{5}{6}\bigg)^n
+-\frac{1}{1-x}.
-+\lim\limits_{n\rightarrow +\infty} \frac{1}{3}\bigg(\frac{1}{6}\bigg)^n
-+\lim\limits_{n\rightarrow +\infty} 2
-\ =\
-,
 </math></center>
-gdzie wykorzystaliśmy znajomość ciągu geometrycznego
+Powołując się ponownie na Wniosek [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy
-(patrz Przykład [[##p.new.am1.w.03.220|Uzupelnic p.new.am1.w.03.220|]]).<br>
-<br>
-'''(2)'''
-'''Sposób I.'''
-Zauważmy, że
-<center><math>\begin{array} {ccccc}
+<center><math>\frac{1}{\left( 1-x \right)^3}
-\displaystyle 0 & \le & \displaystyle\frac{2^{n+1}+3^n}{3^{2n}+2} & \le & \displaystyle\frac{2^{n+1}+3^n}{3^{2n}}\\
+=\sum_{n=0}^{\infty}{ n+2 \choose n}x^n
-\downarrow      &     &                                           &     & \shortparallel\\
+=\frac{1}{2}\sum_{n=0}^{\infty}n^2x^n+\frac{3}{2}\sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n,
-\displaystyle 0 &     &                                           &     & \displaystyle 2\bigg(\frac{2}{9}\bigg)^n+\bigg(\frac{1}{3}\bigg)^n\\
-&     &                                           &     & \downarrow\\
-&     &                                           &     & 0\\
-\end{array}
 </math></center>
-gdzie wykorzystaliśmy znajomość ciągu geometrycznego.
+co w połączeniu z równościami ([[##eq 11|Uzupelnic eq 11|]]) oraz ([[##eq 122|Uzupelnic eq 122|]])
-Zatem korzystając z twierdzenie a trzech ciągach wnioskujemy,
+daje zwartą postać funkcji tworzącej <math>G\!\left( x \right)</math> dla ciągu <math>1,4,9,\ldots,n^2,\ldots</math>:
-że
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} \frac{2^{n+1}+3^n}{3^{2n}+2}=0.</math><br>
-<br>
-'''Sposób II.'''
-Dzieląc licznik i mianownik przez <math>3^{2n}</math>
-oraz korzystając z twierdzeń o arytmetyce granic, mamy
-<center><math>\lim\limits_{n\rightarrow +\infty}\frac{2^{n+1}+3^n}{3^{2n}+2}
+<center><math>G\!\left( x \right)=\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}.
-\lim\limits_{n\rightarrow +\infty} \frac{\displaystyle 2\cdot\bigg(\frac{2}{9}\bigg)^n+\bigg(\frac{1}{3}\bigg)^n}{\displaystyle 1+2\cdot\bigg(\frac{1}{9}\bigg)^n}
-\ =\
-.
 </math></center>
-'''(3)'''
+Naszym zadaniem było jednakże policzenie funkcji tworzącej <math>H(x)</math> dla ciągu
-Korzystając ze wzoru na sumę skończonego
+<math>1,1+4,1+4+9,\ldots,1+4+9+\ldots+n^2,\ldots</math>,
-ciągu geometrycznego (patrz Uwaga [[##u.1.0100|Uzupelnic u.1.0100|]]), mamy
+tzn. ciągu sum początkowych wyrazów ciągu <math>1,4,9,\ldots,n^2,\ldots</math>.
+Aby uzyskać <math>H\!\left( x \right)</math> wystarczy więc skorzystać ze wzoru ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]])
+i podzielić <math>G\!\left( x \right)</math> przez <math>1-x</math>.
+Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej
-<center><math>\lim\limits_{n\rightarrow +\infty}\frac{\displaystyle 1+\frac{1}{4}+\frac{1}{16}+\ldots+\frac{1}{4^n}}{\displaystyle 1+\frac{1}{3}+\frac{1}{9}+\ldots+\frac{1}{3^n}}
+<center><math>H\!\left( x \right)=\frac{G\!\left( x \right)}{1-x}
-\ =\
+=\frac{2}{\left( 1-x \right)^4}-\frac{3}{\left( 1-x \right)^3}+\frac{1}{\left( 1-x \right)^2}.
-\lim\limits_{n\rightarrow +\infty}\frac{\displaystyle\frac{\displaystyle 1-\frac{1}{4^{n+1}}}{\displaystyle 1-\frac{1}{4}}}{\displaystyle\frac{\displaystyle 1-\frac{1}{3^{n+1}}}{\displaystyle 1-\frac{1}{3}}}
-\ =\
-\frac{9}{8}\cdot
-\lim\limits_{n\rightarrow +\infty}\frac{\displaystyle 1-\overbrace{\bigg(\frac{1}{4}\bigg)^{n+1}}^{\rightarrow 0}}{\displaystyle 1-\underbrace{\bigg(\frac{1}{3}\bigg)^{n+1}}_{\rightarrow 0}}
-\ =\
-\frac{9}{8}\cdot 1
-\ =\
-\frac{9}{8}.
 </math></center>
-{}<math>\Box</math></div></div>
+Korzystając po raz kolejny z Wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy
+<center><math>\alignedH\!\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</math></center>
+W konsekwencji zachodzi równość
+<center><math>\sum_{k=1}^nk^2=\left[x^n\right]H\!\left( x \right)=\frac{2n^3+3n+n}{6}.
+</math></center>
+mm
+'''Przykład. '''
+Wracamy  do przykładu z monetami.
+Występowały tam funkcje tworzące postaci
+<center><math>A_k\!\left( x \right) = 1+x^k+x^{2k}+x^{3k}+\ldots,
+</math></center>
-{{cwiczenie|[Uzupelnij]||
+dla <math>k=1,5,10,25</math> i <math>50</math>.
-Niech
+Z równości ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]]) wiemy, że
-<math>\displaystyle\{x_n\}\subseteq\mathbb{R}</math>  będzie ciągiem liczbowym takim, że
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} x_n=g.</math>
-Udowodnić, że
-jeśli <math>g\ne 0</math> oraz
-<math>x_n\ne 0</math> dla dowolnego <math>n\in\mathbb{N},</math> to ciąg
-<math>\displaystyle\big\{\frac{1}{x_n}\big\}</math> jest ograniczony
-oraz dodatkowo
-<center><math>\exists m>0:\ \bigg|\frac{1}{x_n}\bigg|\ge m.
+<center><math>1+x^k+x^{2k}+x^{3k}+\ldots, =\frac{1}{1-x^k}
 </math></center>
-}}
+tak więc:
+<center><math>\alignedA\!\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</math></center>
+skąd natychmiast:
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
+<center><math>\alignedA\!\left( x \right)&=&1+xA\!\left( x \right),\\
-Skorzystać z definicji granicy ciągu z
+B\!\left( x \right)&=&A\!\left( x \right)+x^5B\!\left( x \right),\\
-<math>\displaystyle\varepsilon=\frac{|g|}{2}.</math>
+C\!\left( x \right)&=&B\!\left( x \right)+x^{10}C\!\left( x \right),\\
-{}<math>\Box</math></div></div>
+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</math></center>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+Równości te dają zależności między współczynnikami:
-Niech <math>\displaystyle\lim\limits_{n\rightarrow +\infty} x_n=g\ne 0.</math>
-Niech <math>\displaystyle\varepsilon=\frac{|g|}{2}>0.</math>
-Z definicji granicy mamy
-<center><math>\exists N\in\mathbb{N}\ \forall n\ge N:\
+<center><math>a_n=1,\quad b_n=a_n+b_{n-5},\quad c_n=b_n+c_{n-10},\quad
-|x_n-g|<\frac{|g|}{2},
+d_n=c_n+d_{n-25},\quad e_n=d_n+e_{n-50}.
 </math></center>
-w szczególności dla tak dobranego <math>N\in\mathbb{N},</math> mamy
+Wykorzystując te zależności rekurencyjne możemy wypełnić następującą tabelę:
+{-2cm}
+{| border=1
+|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
+|-
+|
+<math>n</math> || 0 || 5 || 10 || 15 || 2 || 25 || 30 || 35 || 40 || 45 || 50 || 55 || 60 || 65 || 70 || 75 || 80 || 85 || 90 || 95 || 100
+|-
+|
+<math>a_n</math> || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
+|-
+|
+<math>b_n</math> || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19 || 20 || 21
+|-
+|
+<math>c_n</math> || 1 || 2 || 4 || 6 || 9 || 12 || 16 || 10 || 25 || 30 || 36 || 42 || 49 || 56 || 64 || 72 || 81 ||   || 100 ||   || 121
+|-
+|
+<math>d_n</math> || 1 ||   ||   ||   ||   || 13 ||    ||    ||    ||    || 49 ||    ||    ||    ||   || 121 ||    ||   ||     ||   || 242
+|-
+|
+<math>e_n</math> || 1 ||   ||   ||   ||   ||    ||    ||    ||    ||    || 50 ||    ||    ||    ||   ||     ||    ||   ||     ||   || 292
+|-
+|
+|}
+Pół dolara można rozmienić na <math>50</math> sposobów.
+Z kolei rozmieniać jednego dolara można na aż <math>292</math> sposoby.
+Do problemu tego wrócimy jeszcze w następnym wykładzie.
+{| border=1
+|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
+|-
+| '''Funkcje tworzące w rozwiązywaniu zależności rekurencyjnych.'''
+|-
+|
+|}
+mm
-<center><math>\forall n\ge N:\ g-\frac{|g|}{2}<x_n<g+\frac{|g|}{2},
+'''Przykład. '''
+Rozważmy ciąg Fibonacci'ego, tzn. ciąg <math>\left( f_0,f_1,f_2,f_3,\ldots \right)</math>
+zdefiniowany w następujący sposób:
+<center><math>\alignedf_0&=&0,\\
+f_1&=&1,\\
+f_n&=&f_{n-1}+f_{n-2}\quad\textrm{dla}\ n\geq2.
+\endaligned</math></center>
+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 <math>f_n</math> przekładają się natychmiast na
+następujące równanie, jakie musi spełniać funkcja tworząca <math>F\!\left( x \right)</math>
+dla ciągu Fibonacci'ego
+<center><math>F\!\left( x \right)
+=\sum_{n=0}^{\infty}f_nx^n
+=x+\sum_{n=2}^{\infty}\left( f_{n-1}+f_{n-2} \right)x^n=1+x+xF\!\left( x \right)+x^2F\!\left( x \right).
 </math></center>
-zatem
+Przekształcając powyższe równanie otrzymujemy:
-<center><math>\forall n\ge N:\ \frac{|g|}{2}<|x_n|<\frac{3|g|}{2},
+<center><math>
+F\!\left( x \right)=\frac{x}{1-x-x^2}.
 </math></center>
-czyli
+Celem, który chcemy osiągnąć to wykorzystanie funkcji <math>\frac{x}{1-x-x^2}</math>
+do przedstawienia współczynników <math>f_n</math> w postaci zwartej.
+Pierwszym krokiem będzie rozłożenie ułamka w równaniu ([[##eq fib|Uzupelnic eq fib|]])
+na sumę ułamków o mianownikach będących funkcjami liniowymi
-<center><math>\forall n\ge N:\
+<center><math>F\!\left( x \right)=\frac{x}{1-x-x^2}
-\frac{2}{3|g|}<\frac{1}{|x_n|}<\frac{2}{|g|}.
+=\frac{x}{\left( 1-\varphi x \right)\left( 1-\overline{\varphi} x \right)}
+=\frac{1}{\sqrt{5}}\left( \frac{1}{\left( 1-\varphi x \right)}-\frac{1}{\left( 1-\overline{\varphi} x \right)} \right),
 </math></center>
-Zdefiniujmy teraz
+gdzie <math>\varphi=\frac{1+\sqrt{5}}{2}</math> jest złotą liczbą
+oraz <math>\overline{\varphi}=\frac{1-\sqrt{5}}{2}</math> liczbą do niej sprzężoną.
+Korzystając z równania ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]]) otrzymujemy teraz
-<center><math>m
+<center><math>F\!\left( x \right)
-\ =\
+=\frac{1}{\sqrt{5}}\left( \sum_{n=1}^{\infty}{\varphi^nx^n}-\sum_{n=1}^{\infty}{\overline{\varphi}^nx^n} \right)
-\min\bigg\{\frac{2}{3|g|},\frac{1}{|x_1|},\ldots,\frac{1}{|x_n|}\bigg\},\qquad
+=\frac{1}{\sqrt{5}}\sum_{n=1}^{\infty}{\left( \varphi^n-\overline{\varphi}^n \right)x^n}.
-M
-\ =\
-\max\bigg\{\frac{2}{|g|},\frac{1}{|x_1|},\ldots,\frac{1}{|x_n|}\bigg\}.
 </math></center>
-Oczywiście <math>0<m<M</math>
+Tak więc dostajemy szybko znaną nam już postać zwartą
-oraz
+<math>f_n=\frac{1}{\sqrt{5}}\left( \varphi^n-\overline{\varphi}^n \right)</math>.
+Podczas rozwiązywania przykładu związanego z liczbami Fibonacci'ego
+natrafiliśmy na problem polegający na przedstawieniu w postaci szeregu wyrażenia
+<math>\frac{x}{1-x-x^2}</math>.
+Przyjrzymy się dokładniej tego typu wyrażeniom.
+mm
+'''Stopień wielomianu''' <math>{\sf deg}\ P\!\left( x \right)=n</math>,
+jeśli <math>P\!\left( x \right)=p_0+p_1x+\ldots+p_nx^n</math>.
+mm
+mm
+'''Funkcja wymierna''' <math>R\!\left( x \right)</math> to funkcja postaci <math>\frac{P\!\left( x \right)}{Q\!\left( x \right)}</math>, gdzie <math>P\!\left( x \right)</math> oraz <math>Q\!\left( x \right)\neq0</math> są wielomianami skończonego stopnia.
+mm
+Niech <math>A\!\left( x \right)</math> oraz <math>B\!\left( x \right)</math> będą wielomianami
+<math>{\sf deg}\ A\!\left( x \right)\geq {\sf deg}\ B\!\left( x \right)</math>.
+Wtedy istnieją wielomiany <math>Q\!\left( x \right)</math> oraz <math>R\!\left( x \right)</math> takie, że
-<center><math>\forall n\in\mathbb{N}:\ m\le \bigg|\frac{1}{x_n}\bigg|\le M,
+<center><math>A\!\left( x \right)=Q\!\left( x \right)B\!\left( x \right)+R\!\left( x \right),
 </math></center>
-co należało dowieść.
+gdzie <math>{\sf deg}\ R\!\left( x \right)<{\sf deg}\ A\!\left( x \right)={\sf deg}\ Q\!\left( x \right)+{\sf deg}\ B\!\left( x \right)</math>.
-{}<math>\Box</math></div></div>
-{{cwiczenie|[Uzupelnij]||
+mm
+'''Przykład. '''
 Niech
-<math>\displaystyle\{a_n\},\{b_n\}\subseteq\mathbb{R}</math>
-będą ciągami liczbowymi zbieżnymi,
-Udowodnić następujące stwierdzenia:<br>
-'''(1)'''
-<math>\displaystyle \lim\limits_{n\rightarrow +\infty} (a_nb_n)
-=\bigg(\lim\limits_{n\rightarrow +\infty} a_n\bigg)\bigg(\lim\limits_{n\rightarrow +\infty} b_n\bigg)</math>;<br>
-'''(2)'''
-<math>\displaystyle \lim\limits_{n\rightarrow +\infty} \frac{a_n}{b_n}
-=\frac{\lim\limits_{n\rightarrow +\infty} a_n}{\lim\limits_{n\rightarrow +\infty} b_n}</math>
-(o ile
-<math>b_n\ne 0</math> dla <math>n\in\mathbb{N}</math> oraz <math>\displaystyle\lim\limits_{n\rightarrow +\infty} b_n\ne 0</math>).
-}}
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
+<center><math>A\!\left( x \right)=3x^5+5x^4+2x^3+x^2+2\quad\textrm{oraz}\quadB\!\left( x \right)=x^3+2x^2-1.
-'''(1)''' Skorzystać z faktu, że ciąg zbieżny jest ograniczony.
+</math></center>
-Przy liczeniu granicy ciągu <math>\displaystyle\{a_nb_n\}</math> wykorzystać oszacowanie
+Wtedy wielomiany
+<center><math>Q\!\left( x \right)=3x^2-x+3\quad\textrm{oraz}\quadR\!\left( x \right)=x+2
+</math></center>
+spełniają
+<center><math>\alignedA\!\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</math></center>
+Ponadto <math>{\sf deg}\ A\!\left( x \right)=5=2+3={\sf deg}\ Q\!\left( x \right)+{\sf deg}\ B\!\left( x \right)</math>.
+Niech <math>P\!\left( x \right)</math> oraz <math>Q\!\left( x \right)</math> będą wielomianami takimi,
+że <math>{\sf deg}\ P\!\left( x \right)\geq{\sf deg}\ Q\!\left( x \right)</math>.
+Wtedy funkcję wymierną
+<math>R\!\left( x \right)=P\!\left( x \right)/Q\!\left( x \right),
+</math>
+można przedstawić w postaci
-<center><math>\big|a_nb_n-ab\big|
+<center><math>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)},
-\ \le\
-\big|a_nb_n-a_nb\big|
-+\big|a_nb-ab\big|.
 </math></center>
-'''(2)''' Najpierw udowodnić, że
+dla pewnych wielomianów <math>A\!\left( x \right)</math> oraz <math>B\!\left( x \right)</math>
-<math>\displaystyle \lim\limits_{n\rightarrow +\infty} \frac{1}{b_n}
+spełniających <math>{\sf deg}\ B\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>.
-=\frac{1}{\lim\limits_{n\rightarrow +\infty} b_n}.</math>
-W tym celu skorzystać z Zadania [[##z.new.am1.c.04.0040|Uzupelnic z.new.am1.c.04.0040|]].
+Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi <math>R\!\left( x \right)=P\!\left( x \right)/Q\!\left( x \right),
-Następnie wykorzystać punkt (1).
+</math> dla których <math>{\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>.
-{}<math>\Box</math></div></div>
+{{twierdzenie|[Uzupelnij]||
+Niech <math>P\!\left( x \right)</math> oraz <math>Q\!\left( x \right)</math> będą wielomianami takimi, że
+* <math>{\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>,
+* <math>Q\!\left( x \right)=S\!\left( x \right)T\!\left( x \right)</math>,
+gdzie oba wielomiany <math>S\!\left( x \right),T\!\left( x \right)</math> są stopnia co najmniej <math>2</math>,
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+* <math>q_0\neq0</math>.
-'''(1)'''
-Niech <math>\displaystyle\lim\limits_{n\rightarrow +\infty} a_n=a</math> i <math>\displaystyle\lim\limits_{n\rightarrow +\infty} b_n=b.</math>
+Wtedy istnieją wielomiany
-Należy pokazać, że
+<math>A\!\left( x \right)</math> oraz <math>B\!\left( x \right)</math> takie, że
+<math>{\sf deg}\ A\!\left( x \right)<{\sf deg}\ S\!\left( x \right)</math> i
+<math>{\sf deg}\ B\!\left( x \right)<{\sf deg}\ T\!\left( x \right)</math>
+oraz
-<center><math>\forall \varepsilon>0\ \exists N\in\mathbb{N}\ \forall n\ge N:
+<center><math>\frac{P\!\left( x \right)}{Q\!\left( x \right)}
-\big|a_nb_n-ab\big|<\varepsilon.
+=\frac{A\!\left( x \right)}{S\!\left( x \right)}+\frac{B\!\left( x \right)}{T\!\left( x \right)}.
 </math></center>
-Ustalmy dowolne <math>\displaystyle\varepsilon>0.</math>
+}}
-Ciąg <math>\displaystyle\{a_n\}</math> jako zbieżny, jest ograniczony, to znaczy
+{{uwaga|[Uzupelnij]||
-<center><math>\exists A>0\ \forall n\in\mathbb{N}:\ |a_n|\le A.
+Twierdzenie [[##thm PQ <nowiki>=</nowiki> AS BT|Uzupelnic thm PQ <nowiki>=</nowiki> AS BT|]] pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych.
+}}
+{{dowod|[Uzupelnij]||
+[Metoda rozwijania funkcji wymiernej w szereg.]
+Rozważmy funkcję wymierną w postaci
+<center><math>R\!\left( x \right)=\frac{P\!\left( x \right)}{Q\!\left( x \right)},
 </math></center>
-Z definicji granicy mamy
+gdzie <math>{\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>, oraz <math>q_0\neq0</math>.
+Załóżmy ponadto, że wielomian <math>Q\!\left( x \right)</math> rozkłada się na
+następujący iloczyn czynników liniowych
-<center><math>\aligned
+<center><math>Q\!\left( x \right)
-&& \exists N_1\in\mathbb{N}:\ |b_n-b|<\frac{\varepsilon}{2A},\\
+=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}.
-&& \exists N_2\in\mathbb{N}:\ |a_n-a|<\frac{\varepsilon}{2|b|}
+</math></center>
-\endaligned</math></center>
+Warto wspomnieć, że dalecy nie każdy wielomian ma taki rozkład.
+Na przykład <math>1+x^2</math> jest nierozkładalny i nieliniowy.
+Wykorzystując parokrotnie Twierdzenie [[##thm PQ <nowiki>=</nowiki> AS BT|Uzupelnic thm PQ <nowiki>=</nowiki> AS BT|]]
+otrzymujemy wielomiany <math>P_1\!\left( x \right),\ldots,P_k\!\left( x \right)</math> takie, że
-(przy czym jeśli <math>b=0,</math> to ostatnie wyrażenie
+<center><math>R\!\left( x \right)
-<math>\displaystyle\frac{\varepsilon}{2|b|}</math> zastąpmy przez <math>\displaystyle\varepsilon</math>).
+=\frac{P\!\left( x \right)}{Q\!\left( x \right)}=\frac{P_1\!\left( x \right)}{\left( 1-\rho_1x \right)^{m_1}}+\frac{P_2\!\left( x \right)}{\left( 1-\rho_2x \right)^{m_2}}+\ldots+\frac{P_k\!\left( x \right)}{\left( 1-\rho_kx \right)^{m_k}},
+</math></center>
-Niech <math>N=\max\{N_1,N_2\}.</math>
+gdzie <math>{\sf deg}\ P_i\!\left( x \right)<m_i</math>.
-Wówczas dla dowolnego <math>n\ge N,</math> mamy
+Na mocy Obserwacji [[##obs div|Uzupelnic obs div|]] możemy sprowadzić wielomian <math>P_i\!\left( x \right)</math> do
-<center><math>\aligned
+<center><math>\alignedP_i\!\left( x \right)&=&P_i^1\!\left( x \right)\left( 1-\rho_ix \right)+\gamma_{m_i}\\
-\big|a_nb_n-ab\big|
+&=&P_i^2\!\left( x \right)\left( 1-\rho_ix \right)^2+\gamma_{m_i-1}\left( 1-\rho_ix \right)+\gamma_{m_i}\\
-& \le &
+&\vdots&\\
-\big|a_nb_n-a_nb\big|
+&=&\gamma_1\left( 1-\rho_ix \right)^{m_i-1}+\ldots+\gamma_{m_i-1}\left( 1-\rho_ix \right)+\gamma_{m_i},
-+\big|a_nb-ab\big|
-\ =\
-|a_n||b_n-b|+|a_n-a||b|\\
-& < &
-A\cdot\frac{\varepsilon}{2A}
-+\frac{\varepsilon}{2|b|}\cdot |b|
-\ =\
-\varepsilon,
 \endaligned</math></center>
-zatem
+gdzie <math>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</math>.
+W konsekwencji otrzymamy
-<center><math>\lim\limits_{n\rightarrow +\infty} (a_nb_n)
+<center><math>R\!\left( x \right)\ =\ \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)}.
-\ =\
-a\cdot b
-\ =\
-\bigg(\lim\limits_{n\rightarrow +\infty} a_n\bigg)\cdot\bigg(\lim\limits_{n\rightarrow +\infty} b_n\bigg).
 </math></center>
-'''(2)'''
+Mnożąc teraz obie strony przez
-Niech <math>\displaystyle\lim\limits_{n\rightarrow +\infty} a_n=a</math> i <math>\displaystyle\lim\limits_{n\rightarrow +\infty} b_n=b</math>
-(gdzie <math>b_n\ne 0</math> dla <math>n\in\mathbb{N}</math> oraz <math>b\ne 0</math>).
-Pokażemy najpierw, że
-<center><math>\lim\limits_{n\rightarrow +\infty} \frac{1}{b_n}
+<center><math>Q\!\left( x \right)/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}
-=\frac{1}{b}.
 </math></center>
-Ustalmy dowolne <math>\displaystyle\varepsilon>0.</math>
+i porównując współczynniki przy odpowiadających potęgach <math>x^i</math>
-Z Zadania [[##z.new.am1.c.04.0040|Uzupelnic z.new.am1.c.04.0040|]]  wynika, że
+uzyskujemy pewien układ równań, rozwiązanie którego da nam
+poszukiwane współczynniki <math>\gamma_{i,j}</math>.
+Z drugiej strony, z wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] wynika, że
-<center><math>\exists M>0\ \forall n\in\mathbb{N}:\
+<center><math>\frac{1}{\left( 1-\rho x \right)^{m+1}}
-\bigg|\frac{1}{b_n}\bigg|\le M.
+=\sum_{n=1}^{\infty}{ { m+n \choose m } \rho^n x^n}
 </math></center>
-Z definicji granicy,
+i w konsekwencji:
-zastosowanej do
-<math>\displaystyle\widetilde{\varepsilon}=\frac{|b|\varepsilon}{M}</math>, mamy także
-<center><math>\exists N\in\mathbb{N}\ \forall n\ge N:\
+<center><math>
-|b_n-b|<\frac{|b|\varepsilon}{M}.
+[x^n]R\!\left( x \right)\ =\ \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.
 </math></center>
-Wówczas dla <math>n\ge N,</math> mamy
+}}
+mm
+'''Przykład. '''
+Opisaną wyżej metodę ogólną zilustrujemy na przykładzie funkcji
-<center><math>\bigg|\frac{1}{b_n}-\frac{1}{b}\bigg|
+<center><math>R\!\left( x \right)=\frac{x^2}{1-x-x^2+x^3}.
-\ =\
-\bigg|\frac{b-b_n}{bb_n}\bigg|
-\ =\
-|b_n-b|\cdot\bigg|\frac{1}{b}\bigg|\cdot\bigg|\frac{1}{b_n}\bigg|
-\ \le\
-\frac{|b|\varepsilon}{M}\cdot\frac{1}{|b|}\cdot M
-\ =\
-\varepsilon,
 </math></center>
-pokazaliśmy więc, że
+Wielomian <math>1-x-x^2+x^3</math>
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} \frac{1}{b_n}=\frac{1}{b}.</math>
+ma jeden podwójny pierwiastek  <math>x=1</math>
+oraz jeden pojedynczy <math>x=-1</math>.
+Poznana metoda rozwijania funkcji wymiernej w szereg daje więc
-Możemy teraz skorzystać z udowodnionego już punktu (2),
+<center><math>R\!\left( x \right)
-a mianowicie
+=\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}.
+</math></center>
-<center><math>\lim\limits_{n\rightarrow +\infty} \frac{a_n}{b_n}
+Mnożąc obie strony przez <math>\left( 1-x \right)^2\cdot\left( 1+x \right)</math> otrzymujemy:
-\ =\
-\lim\limits_{n\rightarrow +\infty} \bigg(a_n\cdot\frac{1}{b_n}\bigg)
+<center><math>x^2=\alpha\left( 1-x^2 \right)+\beta\left( 1+x \right)+\gamma\left( 1-2x+x^2 \right).
-\ =\
-a\cdot\frac{1}{b}
-\ =\
-\frac{a}{b}.
 </math></center>
-{}<math>\Box</math></div></div>
+Dwa wielomiany są równe,
+gdy współczynniki przy odpowiadających potęgach są sobie równe.
+Wartości <math>\alpha, \beta, \gamma</math> można więc wyliczyć z układu równań
+<center><math>\left\lbrace\begin{array} {rrrcl}
+\alpha & +\ \beta &  +\ \gamma & = & 0\\
+\alpha &          & -\ 2\gamma & = & 0\\
+& -\ \beta &  +\ \gamma & = & 1.
+\end{array} \right.
+</math></center>
+Rozwiązaniem powyższego układu są wartości
+<math>\alpha=-\frac{1}{4},\
+\beta=\frac{1}{2},\
+\gamma=-\frac{1}{4}.
+</math>
+W konsekwencji otrzymujemy szereg
+<center><math>\alignedR\!\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</math></center>
+Jeżeli mianownik <math>Q\!\left( x \right)</math>
+funkcji wymiernej <math>R\!\left( x \right)=\frac{P\!\left( x \right)}{Q\!\left( x \right)}</math>
+posiada jedynie pierwiastki jednokrotne,
+to następne twierdzenie znacznie przyspiesza rozkład  <math>R\!\left( x \right)</math> na sumę.
+{{twierdzenie|[Uzupelnij]||
+Jeśli <math>R\!\left( x \right)=P\!\left( x \right)/Q\!\left( x \right)</math>,
+gdzie <math>Q\!\left( x \right)=q_0\cdot\left( 1-\rho_1x \right)\cdot\ldots\cdot\left( 1-\rho_1x \right)</math>
+i liczby <math>\rho_1,\ldots,\rho_l</math> są parami różne,
+to w przypadku gdy <math>P\!\left( x \right)</math> jest wielomianem stopnia mniejszego niż <math>l</math>, zachodzi
-{{cwiczenie|[Uzupelnij]||
+<center><math>\left[x^n\right]R\!\left( x \right)
+=a_1\rho_1^n+\ldots+a_l\rho_l^n,
+\quad\textrm{dla}\  a_k=\frac{-\rho_k\cdotP\!\left( 1/\rho_k \right)}{Q'\!\left( 1/\rho_k \right)}.
+</math></center>
-Niech
-<math>\displaystyle\{a_n\},\{b_n\}\subseteq\mathbb{R}</math>
-będą ciągami liczbowymi zbieżnymi.
-Udowodnić następujące stwierdzenia:<br>
-'''(1)'''
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} a_n =a\quad
-\Longrightarrow\quad
-\lim\limits_{n\rightarrow +\infty} |a_n|=|a|</math>;<br>
-'''(2)'''
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} a_n =0\quad
-\Longleftrightarrow\quad
-\lim\limits_{n\rightarrow +\infty} |a_n|=0</math>;
 }}
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
+mm
-'''(1)'''
-Udowodnić najpierw prostą nierówność:
+'''Przykład. '''
+Mianownik <math>Q\!\left( x \right)</math> funkcji wymiernej
+<center><math>R\!\left( x \right)=\frac{P\!\left( x \right)}{Q\!\left( x \right)}=\frac{2x}{1-5x-2x^2+24x^3}.
+</math></center>
+ma trzy różne pierwiastki i można <math>R\!\left( x \right)</math> przedstawić jako
+<center><math>R\!\left( x \right)=\frac{2x}{\left( 1+2x \right)\left( 1-3x \right)\left( 1-4x \right)}.
+</math></center>
+Na mocy twierdzenia [[##thm wymierne|Uzupelnic thm wymierne|]] otrzymujemy więc, że
-<center><math>\forall x,y\in\mathbb{R}:\
+<center><math>\left[x^n\right]R\!\left( x \right)=-\frac{2}{15}\left( -2 \right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.
-\big| |x|-|y|\big|
-\ \le\
-|x-y|.
 </math></center>
-'''(2)''' Wykorzystać jedynie definicję granicy ciągu.
+Jak widzieliśmy na przykładzie ciągu Fibonacci'ego,
-{}<math>\Box</math></div></div>
+funkcje tworzące mogą być bardzo pomocne przy szukaniu postaci zwartej
+pewnych ciągów zadanych rekurencyjnie.
+mm
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+'''Jednorodne, liniowe równanie rekurencyjne''' to równanie postaci
-'''(1)'''
-Udowodnimy najpierw, że
-<center><math>\forall x,y\in\mathbb{R}:\
+<center><math>\left\lbrace
-\big| |x|-|y|\big|
+\begin{array} {rcl}
-\ \le\
+r_0&=&c_0,\\
-|x-y|.
+&\cdots&\\
+r_{k-1}&=&c_{k-1},\\
+r_n&=&a_1r_{n-1}+a_2r_{n-2}+\ldots+a_kr_{n-k}\quad\textrm{dla}\ n\geq k,
+\end{array}
+\right.
 </math></center>
-Korzystając z nierówności trójkąta dla
+gdzie <math>c_0,\ldots,c_{k-1},a_1,\ldots,a_k</math> są liczbami rzeczywistymi
-wartości bezwzględnej (metryki euklidesowej w <math>\displaystyle\mathbb{R}</math>), mamy
+(niezależnymi od parametru rekurencyjnego <math>n</math>).
+mm
+Rozważmy najpierw przypadek, gdy <math>k=2</math>, tzn. równanie postaci
+<center><math>
+\left\lbrace
+\begin{array} {rcl}
+r_0&=&c_0,\\
+r_1&=&c_1,\\
+r_n&=&a_1r_{n-1}+a_2r_{n-2}\quad\textrm{dla}\ n\geq 2.
+\end{array}
+\right.
+</math></center>
+Przykładem takiego równania była zależność opisująca ciąg Fibonacci'ego.
+Zastosowanie ostatniej równości z ([[##eq rec 2|Uzupelnic eq rec 2|]])
+do funkcji tworzącej ciągu <math>\left( r_0,r_1,r_2,\ldots \right)</math> daje:
+<center><math>\alignedR\!\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_1xR\!\left( x \right)+a_2x^2R\!\left( x \right),
+\endaligned</math></center>
+tak więc
-<center><math>|x|
+<center><math>R\!\left( x \right)\ =\ \frac{c_0+\left( c_1-a_1c_0 \right)x}{1-a_1x-a_2x^2}
-\ =\
-|x-y+y|
-\ \le\
-|x-y|+|y|,
 </math></center>
-stąd
+Dla funkcji <math>A\!\left( x \right)=1-a_1x-a_2x^2=\left( 1-\rho_1x \right)\left( 1-\rho_2x \right)</math>
+mogą zajść trzy przypadki:
+* <math>\rho_1 \neq \rho_2</math> są różnymi liczbami rzeczywistymi. Wtedy
-<center><math>|x|-|y|
+<center><math>r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n,
-\ \le\
-|x-y|.
 </math></center>
-Analogicznie dostajemy
+gdzie <math>\alpha</math> oraz <math>\beta</math> są liczbami rzeczywistymi.
+* <math>\rho_1 = \rho_2</math>.  Wtedy
-<center><math>|y|-|x|
+<center><math>r_n\ =\ \left( \alpha n+\beta \right)\rho_1^n,
-\ \le\
-|y-x|
-\ =\
-|x-y|.
 </math></center>
-Dwie ostatnie nierówności oznaczają, że
+gdzie <math>\alpha</math> oraz <math>\beta</math> są liczbami rzeczywistymi.
-<center><math>\big| |x|-|y|\big|
+*  <math>\bigtriangledown</math>
-\ \le\
+Wartości <math>\rho_1</math> oraz <math>\rho_2</math> są różnymi liczbami zespolonymi.
-|x-y|,
+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
+<center><math>r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n.
 </math></center>
-co należało dowieść.
+gdzie <math>\alpha</math> oraz <math>\beta</math> 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.
+{<math>\bigtriangleup</math>}
-Załóżmy teraz, że
+Wracamy teraz do ogólnego, jednorodnego liniowego równania rekurencyjnego.
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} a_n=a.</math>
+Analogicznie do przypadku, gdy <math>k=2</math>, otrzymujemy że
-Należy pokazać, że
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} |a_n|=|a|.</math>
-Ustalmy dowolne <math>\displaystyle\varepsilon>0.</math>
-Z definicji granicy mamy
-<center><math>\exists N\in\mathbb{N}\ \forall n\ge N:\
+<center><math>R\!\left( x \right)\ =\ \frac{P\!\left( x \right)}{1-a_1x-a_2x^2-\ldots-a_kx^k},
-|a_n-a|<\varepsilon.
 </math></center>
-Wówczas, korzystając z udowodnionej nierówności,
+gdzie <math>P\!\left( x \right)</math> jest wielomianem co najwyżej stopnia <math>k-1</math>,
-dla <math>n\ge N,</math> mamy
+zależnym od wartości <math>c_0,\ldots,c_{k-1},a_1,\ldots,a_k</math>.
+Korzystając z ogólnej metody rozwijania funkcji wymiernej w szereg,
+możemy odzyskać wyrazy ciągu <math>r_n</math>,
+jako współczynniki <math>[x^n]R\!\left( x \right)</math> zgodnie z równaniem ([[##eq R(x)|Uzupelnic eq R(x)|]]).
-<center><math>\big||a_n|-|a|\big|
+mm
-\ \le\
-|a_n-a|
+'''Przykład. '''
-\ <\
-\varepsilon.
+Równanie rekurencyjne ma następującą postać
+<center><math>\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.
 </math></center>
-Zatem pokazaliśmy, że
+Ostatnia zależność prowadzi do  funkcji tworzącej <math>R\!\left( x \right)</math> spełniającej
-<math>\displaystyle\lim\limits_{n\rightarrow +\infty} |a_n|=|a|.</math><br>
-<br>
-Zauważmy w tym miejscu, że nie jest ogólnie prawdziwa implikacja
-w drugą stronę. Rozważmy bowiem ciąg <math>a_n=(-1)^n</math>.
-Wówczas <math>\lim\limits_{n\rightarrow +\infty} |a_n|=\lim\limits_{n\rightarrow +\infty} 1=1=|1|</math>, , ale ciąg <math>\{a_n\}</math> nie ma
-granicy.<br>
-<br>
-'''(2)'''
-"<math>\displaystyle\Longrightarrow</math>":<br>
-Wynika wprost z punktu (4).<br>
-"<math>\displaystyle\Longleftarrow</math>":<br>
-Niech <math>\displaystyle\lim\limits_{n\rightarrow +\infty} |a_n|=0.</math>
-Należy pokazać, że <math>\displaystyle\lim\limits_{n\rightarrow +\infty} a_n=0.</math>
-Ustalmy dowolne <math>\displaystyle\varepsilon>0.</math>
-Z definicji granicy ciągu mamy
-<center><math>\exists  N\in\mathbb{N}\ \forall n\ge N:\
+<center><math>R\!\left( x \right)=x^2 + xR\!\left( x \right) + x^2R\!\left( x \right) - x^3R\!\left( x \right).
-\big||a_n|-0\big|<\varepsilon.
 </math></center>
-Zatem dla <math>n\ge N,</math> mamy
+Po dokonaniu prostego wyliczenia dostajemy:
-<center><math>|a_n-0|
+<center><math>R\!\left( x \right)=\frac{x^2}{1-x-x^2+x^3}.
-\ =\
-|a_n|
-\ =\
-\big||a_n|\big|
-\ =\
-\big||a_n|-0\big|
-\ <\
-\varepsilon,
 </math></center>
-co oznacza, że <math>\displaystyle\lim\limits_{n\rightarrow +\infty} a_n=0.</math>
+W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg,
-{}<math>\Box</math></div></div>
+wyliczyliśmy współczynniki <math>[x^n]R\!\left( x \right)</math>, a zatem mamy:
+<center><math>r_n=-\frac{1}{4}+\frac{1}{2}\left( n+1 \right) - \frac{1}{4}\left( -1 \right)^n\quad\textrm{dla dowolnego}\ n=0,1,2,3,\ldots.
+</math></center>