Vytvořující funkce pro posloupnost $(a_0, a_1, a_2, \dots)$ je mocninná řada $a(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots$.

Zobecněné kombinační číslo ($r\in \R, k\in\N$): ${r \choose k} = {n(n-1)\cdots(n-k+1) \over k!}$ Zobecněná binomická věta: $(1+x)^r = \sum_{k\ge 0} {r \choose k} x^k$. Důsledek: ${1\over (1-x)^m} = \sum_n {m+n-1 \choose m-1} x^n$.

Vytvořující funkce posloupnosti samých jedniček je $1 \over 1-x$.

Základní úpravy:

$f(x)+g(x)$	$a_0 + b_0, a_1 + b_1, a_2 + b_2, \dots , a_n + b_n, \dots$
$cf(x)$	$ca_0 , ca_1 , ca_2 , \dots , ca_n , \dots$
$xf(x)$	$0, a_0 , a_1 , a_2 , \dots , a_{n-1} , \dots$
$f(x)-a_0 \over x$	$a_1 , a_2 , \dots , a_{n+1} , \dots$
$f(x^2)$	$a_0, 0, a_1 ,0, a_2 ,0, a_3, 0, \dots$
$f(cx)$	$a_0, ca_1, c^2a_2, c^3 a_3, \dots , c^na_{n} , \dots$
$f(x)g(x)$	$a_0b_0 , a_0b_1 + a_1b_0 , a_0b_2 + a_1b_1 + a_2b_0, \dots, \sum_{0\le i \le n} a_ib_{n-i}, \dots$

Vytvořujíci funkce posloupností

Najděte vytvořující funkci následujících posloupností:

1. $1,2,3,4,\dots, n+1, \dots$
   1. pomocí konvoluce
   2. pomocí derivace
   3. pomocí zobecněné binomické věty
2. ${p \choose p}, {p+1 \choose p}, \dots, {p+n \choose p} \dots$

Explicitní vzorec

Najděte explicitní vzorec pro $n$-tý člen posloupností určených následujícími vytvořujícími funkcemi:

1. $a \over b-cx$ pro $a,b,c \in \R-\{0\}$
2. $3x+7 \over (x+2)(x+3)$
3. $20x + 16 \over 2x^2 - x -6$
4. $2x^2 + 7x - 4 \over x^2 - 1$
5. $1+2x \over x^2 + 6x + 9$

Pro matematické úpravy a jiné podúlohy klidně použijte vhodné nástroje.

Obecný postup: jmenovatele rozdělíme na dvojčleny, rozložíme na parciální zlomky a pro každý z nich najdeme vytvořující funkci.

Kombinatoricky definované VF

Najděte vzorce v uzavřeném tvaru (tedy bez nekonečných sum) pro vytvořující funkce následujících posloupností.

1. Posloupnost $(b_n)_{n=0}^\infty$, kde $b_n$ označuje počet způsobů, jak lze číslo $n$ zapsat jako součet libovolného počtu lichých přirozených čísel (na pořadí sčítanců opět záleží). Například $b_4 = 3$, neboť číslo 4 lze zapsat těmito součty: $1 + 3, 3 + 1, 1 + 1 + 1 + 1$.
2. Posloupnost $(c_n)_{n=0}^\infty$ , kde $c_n$ označuje počet způsobů, jak lze číslo $n$ zapsat jako součet jedniček a dvojek (na pořadí sčítanců záleží). Například $c_4 = 5$, neboť číslo 4 lze zapsat těmito součty: $1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2$.

Dokazování rovností

Pro posloupnosti $b_n$ a $c_n$ z předchozího příkladu platí, že pro každé $n \ge 0$ je $c_n$ rovno $b_{n+1}$ .

1. Dokažte to pomocí vytvořujících funkcí.
2. Dokažte to kombinatorickou úvahou.

Vytvořující funkce polynomů

1. Nechť $d$ je přirozené číslo a nechť $P(x)$ je polynom stupně menšího než $d$. Uvažme funkci $f(x) = {P(x) \over (1-x)^d}$. Ukažte, že $f(x)$ je vytvořující funkce pro posloupnost $q(0), q(1), q(2), q(3), \dots$, kde $q(n)$ je nějaký polynom v proměnné $n$ stupně menšího než $d$. (Zdá-li se vám to těžké, rozmyslete nejdřív případy $d = 1$ a $d = 2$.)
2. Rozmyslete, zda platí i opačné tvrzení, tedy že když $q(n)$ je polynom stupně menšího než $d$, tak posloupnost $q(0), q(1), q(2), \dots$ má nutně vytvořující funkci tvaru $P(x) \over (1-x)^d$, kde $P (x)$ je nějaký polynom stupně menšího než $d$.
3. Předpokládejme, že $q(n)$ je polynom stupně $s \in N_0$ . Ukažte, že existuje polynom $r(n)$ stupně $s + 1$ takový, že pro každé $n \in N_0$ platí $r(n) = q(0) + q(1) + q(2) + \cdots + q(n)$. (I zde můžete začít s případy, kdy $s$ je nějaké malé číslo)