Od wzoru rekurencyjnego do wzoru 'jawnego', poprzez funkcję tworzącą

Zadanie 1. (Lista 5. zad.15'.) Znaleźć 'jawny' wzór ciągu zadanego rekurencyjnie: $a_0=0,\ \ a_n=3 a_{n-1}+5^n,\ \mbox{ dla } n\geq 1$.

Rozwiązanie

Krok I. Najpierw znajdujemy funkcję tworzącą $f(x)$ (wykorzystując rekurencję + wzór na sumę postępu geometrycznego):

		$f(x)=\sum\limits_{n=0}^{\infty} a_n \cdot x^n$	$=a_0+\sumka{n=1}(3a_{n-1}+5^n)\cdot x^n=$
			$=a_0+3\cdot\sumka{n=1}a_{n-1}\cdot x^n\ + \ \sumka{n=1}5^n\cdot x^n=$
			$=a_0+3x\cdot\sumka{n=1}a_{n-1}\cdot x^{n-1}\ + \ \sumka{n=1}(5x)^n=$ { O! To ostatnie jest znane! Suma postępu geometrycznego ( 'zapominamy' o warunku: $\|5x\| < 1$ ). }
			$=a_0+3x\cdot\sumka{k=0}a_{k}\cdot x^{k}\ + \ 5x\cdot{1\over 1-5x}=$ { O! Toż tu widać $f(x)$ . }
			$=0+3x\cdot f(x)\ + \ {5x\over 1-5x}.$

Stąd dostajemy $f(x)=0+3x\cdot f(x)\ + \ {5x\over 1-5x},$    czyli     $f(x)\cdot(1-3x)={5x\over 1-5x}.$

Zatem funkcja tworząca jest opisana wzorem     $f(x)={5x\over (1-5x)\cdot(1-3x)}.$

Krok II. Teraz rozkładamy funkcję tworzącą na ułamki proste $f(x)={5x\over (1-5x)\cdot(1-3x)} = {A\over 1-5x}+{B \over 1-3x}$
{ Po co? By zobaczyć dwie sumy dwóch postępów geometrycznych o ilorazach: $(5x)$ oraz $(3x)$ }

Łatwo (choć żmudnie) liczymy:

${5x\over (1-5x)\cdot(1-3x)} \equiv {A(1-3x) +B(1-5x)\over (1-5x)\cdot(1-3x)}$
${5x} \equiv {A(1-3x) +B(1-5x)}$
wstawiając $\ \ x=\frac{1}{5}\ $ obliczamy $\ \ A=...=\frac{5}{2}$;
wstawiając $\ \ x=\frac{1}{3}\ $ obliczamy $\ \ B=...=-\frac{5}{2}$;

skąd dostajemy:
$f(x)=\frac{5}{2}\cdot{1\over 1-5x}-\frac{5}{2}\cdot{1\over 1-3x} .$

Krok III. Teraz funkcję tworzącą przedstawiamy w postaci (jednego) szeregu potęgowego:

$f(x)=\frac{5}{2}\cdot{1\over 1-5x}-\frac{5}{2}\cdot{1\over 1-3x} =$

$=\frac{5}{2}\cdot\sumka{n=0}(5x)^n-\frac{5}{2}\cdot\sumka{n=0}(3x)^n =$

$=\frac{5}{2}\cdot\sumka{n=0}5^n\cdot x^n-\frac{5}{2}\cdot\sumka{n=0}3^n\cdot x^n =$

$=\sumka{n=0} \left( \frac{5}{2}\cdot 5^n\cdot x^n \ -\ \frac{5}{2}\cdot3^n\cdot x^n \right)= $

$=\sumka{n=0} \left( \frac{5}{2}\cdot 5^n \ - \ \frac{5}{2}\cdot 3^n \right)\cdot x^n.$

Krok IV. (deser) Z (niebanalnego) twierdzenia wynika:
Równe szeregi potęgowe mają jednakowe wyrazy (przy tych samych potęgach $x^n$)

Zatem z równości $f(x)=\sumka{n=0}a_n =\sumka{n=0} \left( \frac{5}{2}\cdot 5^n \ - \ \frac{5}{2}\cdot 3^n \right)\cdot x^n$

wynika ostatecznie: $a_n =\left( \frac{5}{2}\cdot 5^n \ - \ \frac{5}{2}\cdot 3^n \right). $

Odp.: $\ \ a_n =\frac{5}{2}\cdot \left( 5^n - 3^n \right). $

Zadanie 2. (Lista 6. zad.7.) Znaleźć funkcję tworzącą ciągu $\ \stylm a_k={k+s\choose k}$.

Rozwiązanie

Zadanie 3. (Lista 7. zad.2.) Wyprowadzić wzory rekurencyjne dla ciągów: $\ \stylm a_n=\left\{{n\atop 2}\right\}\ $ i $\ \stylm b_n=\left\{{n\atop 3}\right\}$,
gdzie $a_0=a_1=0$ oraz $b_0=b_1=b_2=0$. Wyznacz funkcje tworzące: $\ \stylm f_2(x)=\sumka{n=0}\left\{{n\atop 2}\right\}x^n\ $ i $\ \stylm f_3(x) =\sumka{n=0}\left\{{n\atop 3}\right\}x^n$ .

Rozwiązanie

$\stylm\left\{{n\atop k}\right\}$ oznacza liczbę podziałów zbioru $[n]:=\{1,2,\ldots,n\}$ na $k$ niepustych, rozłącznych podzbiorów. Oczywiście $\ \stylm\left\{{n\atop 1}\right\}=1\ $ i $\ \stylm\left\{{n\atop n}\right\}=1$.
Jak można tworzyć różne podziały zbioru $[n]$ na $k$ podzbiorów (dla ustalonego $k,n, \; k\leq n$):
albo bierzemy singleton $\{n\}$ jako elementem podziału i resztę (czyli zbiór $[n-1]$) dzielimy na $k\!-\!1$ podzbiorów,
ALBO
zbiór $[n-1]$ dzielimy na $k$ podzbiorów i do któregoś z nich dołączamy liczbę $n$.
Stąd dostajemy wzór rekurencyjny: $\ \stylm \left\{{n\atop k}\right\}=\left\{{n-1\atop k-1}\right\}+k\cdot \left\{{n-1\atop k}\right\} .$
Zatem dla $k=2,3$ mamy:
$a_n=1+2\cdot a_{n-1},\ $ dla $\ n\geq 2$,
$b_n=a_{n-1}+3\cdot b_{n-1},\ $ dla $\ n\geq 3$.

Obliczymy funkcję tworzącą $f_2(x)$:
$\stylm f_2(x)=\sumka{n=0} a_n x^n= \sumka{n=2} a_n x^n = \ \ \ $ (bo $a_0=a_1=0$)
   $\stylm =\sumka{n=2}\left( 1+2\cdot a_{n-1} \right) x^n=\ \ \ $ (bo od $n=2$ możemy użyć rekurencji)
   $\stylm =\sumka{n=2} x^n +\ 2x\cdot \sumka{n=2}a_{n-1}x^{n-1}= \ \ \ $ ('zwykły' rachunek; pomijamy kwestę zbieżności)
   $\stylm ={x^2\over 1-x}\ +\ 2x\cdot \sumka{i=1}a_{i}x^{i}= \ \ \ $ (suma postępu geometrycznego oraz zmiana wskaźnika)
   $\stylm ={x^2\over 1-x}\ +\ 2x\cdot \sumka{i=0}a_{i}x^{i}= \ \ \ $ (bo $a_0=a_1=0$ ).
   $\stylm ={x^2\over 1-x}\ +\ 2x\cdot f_2(x)$.
Stąd
$\stylm (1-2x)f_2(x)={x^2\over 1-x}$
i ostatecznie:
$\stylm f_2(x)={x^2\over (1-x)(1-2x)}$ .

Obliczymy funkcję tworzącą $f_3(x)$:
$\stylm f_3(x)=\sumka{n=0} b_n x^n= \sumka{n=3} b_n x^n = \ \ \ $ (bo $\ b_0=b_1=b_2=0$)
   $\stylm =\sumka{n=3}\left( a_{n-1}+3\cdot b_{n-1} \right) x^n=\ \ \ $ (bo od $n=3$ możemy użyć rekurencji)
   $\stylm =x\cdot\sumka{n=3}a_{n-1} x^{n-1} +\ 3x\cdot \sumka{n=3}b_{n-1}x^{n-1}= \ \ \ $ ('zwykły' rachunek; pomijamy kwestę zbieżności)
   $\stylm =x\cdot\sumka{i=2}a_{i} x^{i} +\ 3x\cdot \sumka{j=2}b_{j}x^{j}= \ \ \ $ (zmiany wskaźników)
   $\stylm =x\cdot f_2(x)\ +\ 3x\cdot f_3(x) \ \ \ $ (bo bo $\ a_0=a_1=0\ $ i $\ b_0=b_1=b_2=0$) .
Stąd
$\stylm (1-3x)f_3(x)=x\cdot{x^2\over (1-x)(1-2x)}$
i ostatecznie:
$\stylm f_3(x)={x^3\over (1-x)(1-2x)(1-3x)}$ .

Uwaga:

Rozkładając $\stylm {1\over (1-x)(1-2x)(1-3x)}$ na ułamki proste dostajemy:
$\stylm f_3(x)=x^3\cdot\left( \frac{1}{2}\cdot{1\over 1-x} -4\cdot{1\over 1-2x}+\frac{9}{2}\cdot{1\over 1-3x} \right)\ \ \ $ (i stosując wzór na sumę postępu geometrycznego)
$\stylm =x^3\cdot\left( \frac{1}{2}\cdot\sumka{k=0}x^k -4\cdot\sumka{k=0}(2x)^k+\frac{9}{2}\cdot\sumka{k=0}(3x)^k \right)=$
$\stylm =x^3\cdot \sumka{k=0} \left( \frac{1}{2} -4\cdot 2^k+\frac{9}{2}\cdot 3^k \right)x^k=$
$\stylm =\sumka{k=0} \left( \frac{1}{2} - 2^{k+2}+\frac{1}{2}\cdot 3^{k+2} \right)x^{k+3}=\ \ \ $ (i zmieniając wskaźnik)
$\stylm =\sumka{n=3} \left( \frac{1}{2} - 2^{n-1}+\frac{1}{2}\cdot 3^{n-1} \right)x^{n}$
czyli $\ \stylm f_3(x)=\sumka{n=3}b_n x^n = \sumka{n=0} \left( \frac{1}{2} - 2^{n-1}+\frac{1}{2}\cdot 3^{n-1} \right)x^{n} $
i porównując współczynniki w tych dwóch szeregach potęgowych dostajemy (zwięzły) wzór:
$\ \stylm b_n= \frac{1}{2} - 2^{n-1}+\frac{1}{2}\cdot 3^{n-1}, \ $ dla $\ n\geq 3$ .