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

Postup výroby VF z rekurzivně zadané posloupnosti.

• začneme s rovností $a_n x^n = (\hbox{rekurzivní výraz}) x^n$.
• sečteme pro všechna přípustná $n$: $\sum_{n \ge n_0} a_n x^n = \sum_{n \ge n_0} (\hbox{rek. v.}) x^n$.
• upravujeme a všechny nekonečné sumy nahradíme za $f(x)$.
• vyřešíme rovnici, kde neznámá je $f(x)$.

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íci funkce posloupností

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

1. $1, -1, 1, -1, \dots , (-1)^n , \dots$
2. $1,2,3,4,\dots, n+1, \dots$
3. ${p \choose p}, {p+1 \choose p}, \dots, {p+n \choose p} \dots$
4. $1, 1, 2, 2, 4, 4, 8, 8, \dots$

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 $(a_n)_{n=0}^\infty$, kde $a_n$ označuje počet způsobů, jak lze číslo $n$ zapsat jako součet tří lichých přirozených čísel (na pořadí sčítanců záleží). Například $a_7 = 6$, neboť číslo 7 lze zapsat těmito součty: $1 + 1 + 5, 1 + 5 + 1, 5 + 1 + 1, 1 + 3 + 3, 3 + 1 + 3, 3 + 3 + 1$.
2. 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$, nebot’ číslo 4 lze zapsat těmito součty: $1 + 3, 3 + 1, 1 + 1 + 1 + 1$.
3. 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.

Rekurence

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

$$a_n = \left\{ \matrix{1& \hbox{pro $n=0$}\cr 3a_{n-1}-1 & \hbox{pro $n\ge 1$}} \right.$$

$$b_n = \left\{ \matrix{1/2& \hbox{pro $n=0$} \cr 1-\sum_{0\le k \le n-1} b_k & \hbox{pro $n\ge 1$}} \right.$$