Matematyka dyskretna 1/Ćwiczenia 7: Funkcje tworzące

Funkcje tworzące

Ćwiczenie 1

Policz funkcję tworzącą następujących ciągów:

a. $a_n=2^n$ ,

b. $b_n=2n+3$ ,

c. $c_n=\frac{1}{n}$ dla $n\ge 1$ , oraz $c_0=0$ ,

d. $d_n=1+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{n}$ .

Wskazówka

Skorzystaj z obserwacji [obs][obs genfunc tools].

Rozwiązanie

W punktach a. i c. będziemy używać wzoru na postać zwartą funkcji tworzącej ciągu stałego równego $1$ :

$\frac{1}{1-x}=1+x+x^2+x^3+x^4+\dots .$      (1)

ad a. Dla funkcji tworzącej $A\left(x\right)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots$, korzystając z (1), otrzymujemy równość

$A\left(x\right)=1+2x+2^2{x}^2+2^3{x}^3+\dots =\frac{1}{1-2x}.$

ad b. Korzystając z Wniosku 7.5 otrzymamy

$\frac{1}{{(1-x)}^2}=1+2x+3x^2+4x^3+5x^4+\dots$      (2)

Funkcja $\frac{1}{1-x}$ jest funkcją tworzącą ciągu stałego równego $1$ , zaś funkcja $\frac{1}{{(1-x)}^2}$ jest funkcją tworzącą ciągu $n+1$ . Tak więc, aby otrzymać funkcję tworzącą ciągu $2n+3$ wystarczy dodać jedną do podwojonej drugiej:

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

ad c. Funkcja tworząca $C\left(x\right)=c_0+c_{1}x+c_2{x}^2+c_3{x}^3+\dots$ jest, na mocy [eq][eq wzor z calka], równa całce z funkcji $\frac{1}{1-x}$ , czyli

$C\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n}=\int \sum _{n=0}^{\mathrm{\infty }}{x}^n=\int \frac{1}{1-x}=-\ln (1-x).$

ad d. Korzystając z punktu c., na mocy [eq][eq 1 przez 1-x], otrzymujemy

$D\left(x\right)=\frac{C\left(x\right)}{1-x}=-\frac{\ln (1-x)}{1-x}=\frac{\ln (1-x)}{x-1}.$

Ćwiczenie 2

Policz funkcję tworzącą ciągu $a_n=\frac{1}{n!}$ .

Wskazówka

Dla funkcji tworzącej $A\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}$ zachodzi $A^{\prime }\left(x\right)=A\left(x\right)$ . Rozważ jakie funkcje mają tę własność?

Rozwiązanie

Niech

$A\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}.$

Korzystając z obserwacji [obs][obs genfunc tools] zauważmy, że

$A^{\prime }\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}\frac{\left(x^n\right)}{n!}=\sum _{n=1}^{\mathrm{\infty }}\frac{n{x}^{n-1}}{n!}=\sum _{n=1}^{\mathrm{\infty }}\frac{x^{n-1}}{(n-1)!}=\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}=A\left(x\right).$

Po podstawieniu w miejsce $A\left(x\right)$ funkcji $e^{B\left(x\right)}$ uzyskamy:

$e^{B\left(x\right)}=\left(e^{B\left(x\right)}\right)=B^{\prime }\left(x\right)e^{B\left(x\right)},$

co implikuje, że $B^{\prime }\left(x\right)=1$ , a więc $B\left(x\right)=x+a$ dla pewnego $a\in \mathbb{ℝ}$ . Z faktu, że $A\left(0\right)=1$ mamy więc:

$A\left(x\right)=e^x.$

Ćwiczenie 3

Pokaż, że dla liczby naturalnej $m$ zachodzi

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

Wskazówka

Rozpisz uogólniony symbol dwumianowy z Twierdzenia 7.4.

Rozwiązanie

Niech

$G\left(x\right)=\frac{1}{{(1-x)}^{m+1}}.$

Korzystając z Twierdzenia 7.4 otrzymujemy równość:

$G\left(x\right)={(1+(-x))}^{-(m+1)}=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{-(m+1)}{n}){(-x)}^n.$

Po rozpisaniu uogólnionego symbolu dwumianowego $(\genfrac{}{}{0ex}{}{y}{n})=\frac{y^{\underset{\_}{n}}}{n!}$ funkcja $G\left(x\right)$ przyjmuje więc postać:

$\begin{array}{rlr}& & \sum _{n=0}^{\mathrm{\infty }}\frac{(-m-1)\cdot (-m-2)\cdot \dots \cdot (-m-n)}{n!}{(-1)}^n{x}^n=\\ & & =\sum _{n=0}^{\mathrm{\infty }}\frac{(m+n)\cdot (m+n-1)\cdot \dots \cdot (m+1)}{n!}{x}^n.\end{array}$

Korzystając ponownie z definicji symbolu dwumianowego dostajemy:

$G\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{m+n}{n})x^n.$

Ćwiczenie 4

Przedstaw funkcję

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

w postaci szeregu funkcyjnego.

Wskazówka

Wielomian $1-3x-2x^2+2x^3$ ma miejsce zerowe dla $x=-1$ .

Rozwiązanie

Wielomian $W\left(x\right)=1-3x-2x^2+2x^3$ ma miejsce zerowe $x=-1$ , czyli $W\left(x\right)=(1-4x+2x^2)(1+x)$ . Z kolei funkcja kwadratowa $1-4x+2x^2$ ma miejsca zerowe:

$x_1=\frac{2+\sqrt{2}}{2},x_2=\frac{2-\sqrt{2}}{2},$

co implikuje

$W\left(x\right)=(1-(2+\sqrt{2})x)\cdot (1-(2-\sqrt{2})x)\cdot (1+x).$

Funkcja $W\left(x\right)$ ma więc postać

$G\left(x\right)=\frac{1+2x-6x^2}{1-3x-2x^2+2x^3}=\frac{A}{1-(2+\sqrt{2})x}+\frac{B}{1-(2-\sqrt{2})x}+\frac{C}{1+x},$

dla pewnych $A,B,C\in \mathbb{ℝ}$ . Po wymnożeniu przez $1-3x-2x^2+2x^3$ otrzymamy:

$\begin{array}{rl}1+2x-6x^2& =A(1-(2-\sqrt{2})x)(1+x)+B(1-(2+\sqrt{2})x)(1+x)\\ & +C(1-(2-\sqrt{2})x)(1-(2+\sqrt{2})x)\\ & =(A+B+C)+((-1-\sqrt{2})A+(-1+\sqrt{2})B-4C)x\\ & +((-2-\sqrt{2})A+(-2+\sqrt{2})B+2C)x^2.\end{array}$

Dwa wielomiany są równe wtedy i tylko wtedy, gdy współczynniki stojące przy odpowiednich wyrazach $x^n$ są sobie równe. Przyrównujemy więc współczynniki stojące przed $x^0,x^1,x^2$ i otrzymujemy układ równań:

$\{\begin{array}{rl}1& =A+B+C\\ 2& =(-1-\sqrt{2})A+(-1+\sqrt{2})B-4C\\ -6& =(-2-\sqrt{2})A+(-2+\sqrt{2})B+2C,\end{array}$

którego rozwiązaniem są $A=B=1,C=-1$ . Funkcja $G\left(x\right)$ po podstawieniu za $A,B,C$ odpowiednio liczb $1,1,-1$ , jest sumą

$G\left(x\right)=\frac{1}{1-(2+\sqrt{2})x}+\frac{1}{1-(2-\sqrt{2})x}-\frac{1}{1+x}.$

Rozwijając ułamki postaci $\frac{\alpha }{1-\rho x}$ w szereg funkcyjny $\alpha \sum _{n=0}^{\mathrm{\infty }}{\rho }^n{x}^n$ otrzymujemy:

$G\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}({(2+\sqrt{2})}^n+{(2-\sqrt{2})}^n-{(-1)}^n)x^n,$

czyli jest to funkcja tworząca ciągu

${(2+\sqrt{2})}^n+{(2-\sqrt{2})}^n-{(-1)}^n$

Ćwiczenie 5

Rozwiąż równanie rekurencyjne:

$\{\begin{array}{rl}{a}_0& =0,\\ a_1& =1,\\ a_n& =2a_{n-1}-a_{n-2},\text{dla}n\ge 2.\end{array}$

Wskazówka

Rozłóż funkcje kwadratową $1-2x+x^2=(1-{\rho }_{1}x)(1-{\rho }_{2}x)$ i w zależności od wartości ${\rho }_1,{\rho }_2$ skorzystaj z metody rozwiązania jednorodnego, liniowego równania rekurencyjnego, gdy $k=2$ podanej w wykładzie.

Rozwiązanie

Korzystając ze wzoru z wykładu Funkcje tworzące, dla rozwiązania jednorodnego, liniowego równania rekurencyjnego przy $k=2$ otrzymamy następującą funkcję kwadratową:

$1-2x+x^2={(1-x)}^2.$

Jest to przypadek, gdy pierwiastki są sobie równe, więc rozwiązanie jest postaci

$a_n=(\alpha n+\beta )1^n,$

gdzie $\alpha$ oraz $\beta$ są liczbami rzeczywistymi. Mając podane wyrazy $a_0$ oraz $a_1$ możemy wyliczyć $\alpha$ oraz $\beta$ z następującego układu równań:

$\{\begin{array}{rl}0& =\alpha \cdot 0+\beta ,\\ 1& =\alpha \cdot 1+\beta .\end{array}$

Rozwiązaniem są więc $\alpha =1$ i $\beta =0$ , a zatem

$a_n=n,$

dla $n=0,1,2,3,\dots$ .

Ćwiczenie 6

Rozwiąż równanie rekurencyjne postaci

$\{\begin{array}{rl}{a}_0& =0,\\ a_1& =1,\\ a_n& =a_{n-1}-a_{n-2}\text{dla}n\ge 2.\end{array}$

i sprawdź, czy ciąg $a_n$ jest ograniczony.

Wskazówka

Rozłóż funkcje kwadratową $1-x+x^2=(1-{\rho }_{1}x)(1-{\rho }_{2}x)$ i w zależności od wartości ${\rho }_1,{\rho }_2$ skorzystaj z metody rozwiązania jednorodnego, liniowego równania rekurencyjnego, gdy $k=2$ podanej w wykładzie.

Rozwiązanie

Korzystając ze wzoru z wykładu Funkcje tworzące, dla rozwiązania jednorodnego, liniowego równania rekurencyjnego przy $k=2$ otrzymamy następującą funkcję kwadratową:

$1-x+x^2=(1-\frac{1+i\sqrt{3}}{2}x)(1-\frac{1-i\sqrt{3}}{2}x).$

W tym przypadku pierwiastki są różnymi liczbami zespolonymi, więc rozwiązanie jest postaci

$a_n=\alpha {\left(\frac{1+i\sqrt{3}}{2}\right)}^n+\beta {\left(\frac{1-i\sqrt{3}}{2}\right)}^n,$

gdzie $\alpha$ oraz $\beta$ są liczbami zespolonymi. Mając podane wyrazy $a_0$ oraz $a_1$ możemy wyliczyć $\alpha$ oraz $\beta$ z następującego układu równań:

$\{\begin{array}{rl}0& =\alpha \cdot 1+\beta \cdot 1,\\ 1& =\alpha \cdot \frac{1+i\sqrt{3}}{2}+\beta \cdot \frac{1-i\sqrt{3}}{2}.\end{array}$

Rozwiązaniem są $\alpha =-\frac{i\sqrt{3}}{3}$ i $\beta =\frac{i\sqrt{3}}{3}$ , więc

$a_n=-\frac{i\sqrt{3}}{3}{\left(\frac{1+i\sqrt{3}}{2}\right)}^n+\frac{i\sqrt{3}}{3}{\left(\frac{1-i\sqrt{3}}{2}\right)}^n,$

dla $n=0,1,2,3,\dots$. Z faktu, że

${\left(\frac{1+i\sqrt{3}}{2}\right)}^6=1,{\left(\frac{1-i\sqrt{3}}{2}\right)}^6=1,$

uzyskujemy

$a_n=-\frac{i\sqrt{3}}{3}{\left(\frac{1+i\sqrt{3}}{2}\right)}^{nmod6}+\frac{i\sqrt{3}}{3}{\left(\frac{1-i\sqrt{3}}{2}\right)}^{nmod6}.$

Widzimy więc, że ciąg o wyrazach $a_n=a_{nmod6}$ przybiera cyklicznie wartości pierwszych $6$ -ciu swoich wyrazów. Początkowe wartości ciągu $a_n$ , to

$a_0=0,a_1=1,a_2=1,a_3=0,a_4=-1,a_5=-1.$

Ciąg $a_n$ przybiera więc cyklicznie wartości ze zbioru $\{-1,0,1\}$ , co implikuje oszacowanie

$\left|a_n\right|\le 1$ dla $n=0,1,2,3,\dots .$

Ćwiczenie 7

Rozwiąż równanie rekurencyjne postaci

$\{\begin{array}{rl}{a}_0& =1,\\ a_1& =5,\\ a_2& =11,\\ a_n& =3a_{n-1}+2a_{n-2}-2a_{n-3}\text{dla}n\ge 3.\end{array}$

Wskazówka

Używając równania rekurencyjnego, znajdź zależność dla funkcji tworzącej $A\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$ tego ciągu. Następnie przedstaw funkcję $A\left(x\right)$ w postaci zwartej i wylicz $a_n$ .

Rozwiązanie

Niech $A\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$ . Po podstawieniu równości z równania rekurencyjnego otrzymujemy:

$\begin{array}{rl}\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n& =1+5x+11x^2+3x\sum _{n=2}^{\mathrm{\infty }}{a}_n{x}^n+2x^2\sum _{n=1}^{\mathrm{\infty }}{a}_n{x}^n-2x^3\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n\\ & =1+2x-6x^2+3x\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n+2x^2\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n-2x^3\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n.\end{array}$

W miejsce $\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$ wstawiamy $A\left(x\right)$ i otrzymujemy:

$A\left(x\right)=1+2x-6x^2+3xA\left(x\right)+2x^{2}A\left(x\right)-2x^{3}A\left(x\right).$

Otrzymane równanie przekształcamy do postaci

$A\left(x\right)=\frac{1+2x-6x^2}{1-3x-2x^2+2x^3}.$

W ćwiczeniu 4 przedstawiliśmy funkcję $A\left(x\right)$ w postaci szeregu funkcyjnego:

$\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n=\sum _{n=0}^{\mathrm{\infty }}({(2+\sqrt{2})}^n+{(2-\sqrt{2})}^n-{(-1)}^n)x^n.$

W konsekwencji:

$a_n={(2+\sqrt{2})}^n+{(2-\sqrt{2})}^n-{(-1)}^n$

dla $n=0,1,2,\dots$ .