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

From Studia Informatyczne

Funkcje tworzące

Ćwiczenie 1

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

a. \displaystyle a_n=2^n ,
b. \displaystyle b_n=2n+3 ,
c. \displaystyle c_n=\frac{1}{n} dla \displaystyle n\geq 1 , oraz \displaystyle c_0=0 ,
d. \displaystyle d_n=1+\frac{1}{2}+\frac{1}{3}+\ldots+\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 \displaystyle 1 :


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


ad a. Dla funkcji tworzącej \displaystyle A\!\left( x \right)=a_0+a_1x+a_2x^2+a_3x^3+\ldots, korzystając z (1), otrzymujemy równość

\displaystyle A\!\left( x \right)=1+2x+2^2x^2+2^3x^3+\ldots=\frac{1}{1-2x}.


ad b. Korzystając z Wniosku 7.5 otrzymamy

\displaystyle  \frac{1}{\left( 1-x \right)^2}=1+2x+3x^2+4x^3+5x^4+\ldots      (2)

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


\displaystyle \sum_{n=0}^{\infty}{\left( 2n+3 \right)x^n} = \sum_{n=0}^{\infty}{x^n}+ 2\sum_{n=0}^{\infty}{\left( n+1 \right)x^n} =\frac{1}{1-x}+\frac{2}{\left( 1-x \right)^2} =\frac{3-x}{\left( 1-x \right)^2}

ad c. Funkcja tworząca \displaystyle C\!\left( x \right)=c_0+c_1x+c_2x^2+c_3x^3+\ldots jest, na mocy [eq][eq wzor z calka], równa całce z funkcji \displaystyle \frac{1}{1-x} , czyli

\displaystyle C\!\left( x \right) =\sum_{n=0}^{\infty}{\frac{x^n}{n}} =\int\sum_{n=0}^{\infty}{x^n} = \int \frac{1}{1-x} =-\ln{\left( 1-x \right)}.

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

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

Ćwiczenie 2

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

Wskazówka

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

Rozwiązanie

Niech


\displaystyle A\!\left( x \right) =\sum_{n=0}^{\infty}\frac{x^n}{n!}.


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


\displaystyle A'\!\left( x \right) =\sum_{n=0}^{\infty}\frac{\left( x^n \right)'}{n!} =\sum_{n=1}^{\infty}\frac{n x^{n-1}}{n!} =\sum_{n=1}^{\infty}\frac{x^{n-1}}{\left( n-1 \right)!} =\sum_{n=0}^{\infty}\frac{x^n}{n!}=A\!\left( x \right).


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


\displaystyle e^{B\!\left( x \right)}=\left( e^{B\!\left( x \right)} \right)'=B'\!\left( x \right)e^{B\!\left( x \right)},


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


\displaystyle A\!\left( x \right)=e^x.


Ćwiczenie 3

Pokaż, że dla liczby naturalnej \displaystyle m zachodzi


\displaystyle \frac{1}{\left( 1-x \right)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.


Wskazówka

Rozpisz uogólniony symbol dwumianowy z Twierdzenia 7.4.

Rozwiązanie

Niech


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


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


\displaystyle G\!\left( x \right) =\left( 1+\left( -x \right) \right)^{-\left( m+1 \right)} =\sum_{n=0}^{\infty}{ -\left( m+1 \right) \choose n }\left( -x \right)^n.


Po rozpisaniu uogólnionego symbolu dwumianowego \displaystyle { y \choose n }=\frac{y^{\underline{n}}}{n!} funkcja \displaystyle G\!\left( x \right) przyjmuje więc postać:


\displaystyle \aligned &&\sum_{n=0}^{\infty}\frac{\left( -m-1 \right)\cdot\left( -m-2 \right)\cdot\ldots\cdot\left( -m-n \right)}{n!}\left( -1 \right)^n x^n\ =\\ &&\quad\quad\quad\quad\quad\quad\quad\quad\quad=\ \sum_{n=0}^{\infty}\frac{\left( m+n \right)\cdot\left( m+n-1 \right)\cdot\ldots\cdot\left( m+1 \right)}{n!}x^n. \endaligned


Korzystając ponownie z definicji symbolu dwumianowego dostajemy:


\displaystyle G\!\left( x \right)=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.


Ćwiczenie 4

Przedstaw funkcję


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


w postaci szeregu funkcyjnego.

Wskazówka

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

Rozwiązanie

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


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


co implikuje


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


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


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


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


\displaystyle \aligned 1+2x-6x^2&= A\left( 1-\left( 2-\sqrt{2} \right)x \right)\left( 1+x \right) +B\left( 1-\left( 2+\sqrt{2} \right)x \right)\left( 1+x \right)\\ &+C\left( 1-\left( 2-\sqrt{2} \right)x \right)\left( 1-\left( 2+\sqrt{2} \right)x \right)\\ &=\left( A+B+C \right)+\left( \left( -1-\sqrt{2} \right)A+\left( -1+\sqrt{2} \right)B-4C \right)x\\ &+\left( \left( -2-\sqrt{2} \right)A+\left( -2+\sqrt{2} \right)B+2C \right)x^2. \endaligned


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


\displaystyle \left\lbrace \aligned 1&=A+B+C\\ 2&=\left( -1-\sqrt{2} \right)A+\left( -1+\sqrt{2} \right)B-4C\\ -6&=\left( -2-\sqrt{2} \right)A+\left( -2+\sqrt{2} \right)B+2C, \endaligned  \right.


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


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


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


\displaystyle G\!\left( x \right) =\sum_{n=0}^{\infty}\left( \left( 2+\sqrt{2} \right)^n+\left( 2-\sqrt{2} \right)^n-\left( -1 \right)^n \right)x^n,


czyli jest to funkcja tworząca ciągu


\displaystyle \left( 2+\sqrt{2} \right)^n+\left( 2-\sqrt{2} \right)^n-\left( -1 \right)^n


Ćwiczenie 5

Rozwiąż równanie rekurencyjne:


\displaystyle \left\lbrace \aligned a_0&=0,\\ a_1&=1,\\ a_n&=2a_{n-1}-a_{n-2},\quad\textrm{dla}\ n\geq2. \endaligned  \right.

Wskazówka

Rozłóż funkcje kwadratową \displaystyle 1-2x+x^2=\left( 1-\rho_1x \right)\left( 1-\rho_2x \right) i w zależności od wartości \displaystyle \rho_1,\rho_2 skorzystaj z metody rozwiązania jednorodnego, liniowego równania rekurencyjnego, gdy \displaystyle 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 \displaystyle k=2 otrzymamy następującą funkcję kwadratową:


\displaystyle 1-2x+x^2=\left( 1-x \right)^2.


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


\displaystyle a_n = \left( \alpha n+\beta \right)1^n,


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


\displaystyle \left\lbrace \aligned 0&=\alpha\cdot0+\beta,\\ 1&=\alpha\cdot1+\beta. \endaligned  \right.


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


\displaystyle a_n=n,


dla \displaystyle n=0,1,2,3,\ldots .

Ćwiczenie 6

Rozwiąż równanie rekurencyjne postaci


\displaystyle \left\lbrace \aligned a_0&=0,\\ a_1&=1,\\ a_n&=a_{n-1}-a_{n-2}\quad\textrm{dla}\ n\geq2. \endaligned  \right.


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

Wskazówka

Rozłóż funkcje kwadratową \displaystyle 1-x+x^2=\left( 1-\rho_1x \right)\left( 1-\rho_2x \right) i w zależności od wartości \displaystyle \rho_1,\rho_2 skorzystaj z metody rozwiązania jednorodnego, liniowego równania rekurencyjnego, gdy \displaystyle 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 \displaystyle k=2 otrzymamy następującą funkcję kwadratową:


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


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


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


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


\displaystyle \left\lbrace \aligned 0&=\alpha\cdot1+\beta\cdot1,\\ 1&=\alpha\cdot\frac{1+i\sqrt{3}}{2}+\beta\cdot\frac{1-i\sqrt{3}}{2}. \endaligned  \right.


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


\displaystyle 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 \displaystyle n=0,1,2,3,\ldots. Z faktu, że


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


uzyskujemy


\displaystyle a_n = -\frac{i\sqrt{3}}{3}\left( \frac{1+i\sqrt{3}}{2} \right)^{n \mod 6}+\frac{i\sqrt{3}}{3}\left( \frac{1-i\sqrt{3}}{2} \right)^{n \mod 6}.


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


\displaystyle a_0=0,\quad a_1=1,\quad a_2=1,\quad a_3=0,\quad a_4=-1,\quad a_5=-1.


Ciąg \displaystyle a_n przybiera więc cyklicznie wartości ze zbioru \displaystyle \left\lbrace -1,0,1 \right\rbrace , co implikuje oszacowanie


\displaystyle \left\vert a_n \right\vert\leq 1\quad dla \displaystyle  \ n=0,1,2,3,\ldots.


Ćwiczenie 7

Rozwiąż równanie rekurencyjne postaci


\displaystyle \left\lbrace \aligned a_0&=1,\\ a_1&=5,\\ a_2&=11,\\ a_n&=3a_{n-1}+2a_{n-2}-2a_{n-3}\quad\textrm{dla}\ n\geq3. \endaligned  \right.


Wskazówka

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

Rozwiązanie

Niech \displaystyle A\!\left( x \right)=\sum_{n=0}^{\infty}a_n x^n . Po podstawieniu równości z równania rekurencyjnego otrzymujemy:


\displaystyle \aligned \sum_{n=0}^{\infty}a_n x^n&=1+5x+11x^2+3x\sum_{n=2}^{\infty}a_n x^n+2x^2\sum_{n=1}^{\infty}a_n x^n-2x^3\sum_{n=0}^{\infty}a_n x^n\\ &=1+2x-6x^2 +3x\sum_{n=0}^{\infty}a_n x^n+2x^2\sum_{n=0}^{\infty}a_n x^n-2x^3\sum_{n=0}^{\infty}a_n x^n. \endaligned


W miejsce \displaystyle \sum_{n=0}^{\infty}a_n x^n wstawiamy \displaystyle A\!\left( x \right) i otrzymujemy:


\displaystyle A\!\left( x \right)= 1+2x-6x^2 +3xA\!\left( x \right)+2x^2A\!\left( x \right)-2x^3A\!\left( x \right).


Otrzymane równanie przekształcamy do postaci


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


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


\displaystyle \sum_{n=0}^{\infty}a_n x^n=\sum_{n=0}^{\infty}\left( \left( 2+\sqrt{2} \right)^n+\left( 2-\sqrt{2} \right)^n-\left( -1 \right)^n \right)x^n.


W konsekwencji:


\displaystyle a_n=\left( 2+\sqrt{2} \right)^n+\left( 2-\sqrt{2} \right)^n-\left( -1 \right)^n


dla \displaystyle n=0,1,2,\ldots .