Matematyka dyskretna 1/Ćwiczenia 7: Funkcje tworzące: Różnice pomiędzy wersjami

← poprzednia edycja

WizualnieWikikod

Aktualna wersja na dzień 21:47, 11 wrz 2023

Funkcje tworzące

Ćwiczenie 1

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

a. $a_{n} = 2^{n}$ ,
b. $b_{n} = 2 n + 3$ ,
c. $c_{n} = \frac{1}{n}$ dla $n \geq 1$ , oraz $c_{0} = 0$ ,
d. $d_{n} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ .

Wskazówka

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 (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots$ , korzystając z (1), otrzymujemy równość

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

ad b. Korzystając z Wniosku 7.5 otrzymamy

$\frac{1}{{(1 - x)}^{2}} = 1 + 2 x + 3 x^{2} + 4 x^{3} + 5 x^{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 $2 n + 3$ wystarczy dodać jedną do podwojonej drugiej:

\sum_{n = 0}^{\infty} (2 n + 3) x^{n} = \sum_{n = 0}^{\infty} x^{n} + 2 \sum_{n = 0}^{\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 (x) = 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 (x) = \sum_{n = 0}^{\infty} \frac{x^{n}}{n} = \int \sum_{n = 0}^{\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 (x) = \frac{C (x)}{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 (x) = \sum_{n = 0}^{\infty} \frac{x^{n}}{n!}$ zachodzi $A^{'} (x) = A (x)$ . Rozważ jakie funkcje mają tę własność?

Rozwiązanie

Niech

A (x) = \sum_{n = 0}^{\infty} \frac{x^{n}}{n!}

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

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

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

e^{B (x)} = (e^{B (x)}) = B^{'} (x) e^{B (x)}

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

A (x) = e^{x}

Ćwiczenie 3

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

\frac{1}{{(1 - x)}^{m + 1}} = \sum_{n = 0}^{\infty} (\binom{m + n}{n}) x^{n}

Wskazówka

Rozwiązanie

Niech

G (x) = \frac{1}{{(1 - x)}^{m + 1}}

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

G (x) = {(1 + (- x))}^{- (m + 1)} = \sum_{n = 0}^{\infty} (\binom{- (m + 1)}{n}) {(- x)}^{n}

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

\begin{aligned} \sum_{n = 0}^{\infty} \frac{(- m - 1) \cdot (- m - 2) \cdot \dots \cdot (- m - n)}{n!} {(- 1)}^{n} x^{n} = & = \sum_{n = 0}^{\infty} \frac{(m + n) \cdot (m + n - 1) \cdot \dots \cdot (m + 1)}{n!} x^{n} \end{aligned}

Korzystając ponownie z definicji symbolu dwumianowego dostajemy:

G (x) = \sum_{n = 0}^{\infty} (\binom{m + n}{n}) x^{n}

Ćwiczenie 4

Przedstaw funkcję

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

w postaci szeregu funkcyjnego.

Wskazówka

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

Rozwiązanie

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

x_{1} = \frac{2 + \sqrt{2}}{2}, x_{2} = \frac{2 - \sqrt{2}}{2}

co implikuje

W (x) = (1 - (2 + \sqrt{2}) x) \cdot (1 - (2 - \sqrt{2}) x) \cdot (1 + x)

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

G (x) = \frac{1 + 2 x - 6 x^{2}}{1 - 3 x - 2 x^{2} + 2 x^{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 ℝ$ . Po wymnożeniu przez $1 - 3 x - 2 x^{2} + 2 x^{3}$ otrzymamy:

\begin{aligned} 1 + 2 x - 6 x^{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 - 4 C) x \\ + ((- 2 - \sqrt{2}) A + (- 2 + \sqrt{2}) B + 2 C) x^{2} \end{aligned}

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ń:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{align} 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 \end{align} \right}

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

G (x) = \frac{1}{1 - (2 + \sqrt{2}) x} + \frac{1}{1 - (2 - \sqrt{2}) x} - \frac{1}{1 + x}

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

G (x) = \sum_{n = 0}^{\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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{align} a_0&=0,\\ a_1&=1,\\ a_n&=2a_{n-1}-a_{n-2},\quad\text{dla}\ n\geq2. \end{align} \right}

Wskazówka

Rozłóż funkcje kwadratową $1 - 2 x + x^{2} = (1 - ρ_{1} x) (1 - ρ_{2} x)$ i w zależności od wartości $ρ_{1}, ρ_{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 - 2 x + x^{2} = {(1 - x)}^{2}

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

a_{n} = (α n + β) 1^{n}

,

gdzie $α$ oraz $β$ są liczbami rzeczywistymi. Mając podane wyrazy $a_{0}$ oraz $a_{1}$ możemy wyliczyć $α$ oraz $β$ z następującego układu równań:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{align} 0&=\alpha\cdot0+\beta,\\ 1&=\alpha\cdot1+\beta. \end{align} \right}

Rozwiązaniem są więc $α = 1$ i $β = 0$ , a zatem

a_{n} = n

,

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

Ćwiczenie 6

Rozwiąż równanie rekurencyjne postaci

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{align} a_0&=0,\\ a_1&=1,\\ a_n&=a_{n-1}-a_{n-2}\quad\text{dla}\ n\geq2. \end{align} \right}

i sprawdź, czy ciąg $a_{n}$ jest ograniczony.

Wskazówka

Rozłóż funkcje kwadratową $1 - x + x^{2} = (1 - ρ_{1} x) (1 - ρ_{2} x)$ i w zależności od wartości $ρ_{1}, ρ_{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} = α {(\frac{1 + i \sqrt{3}}{2})}^{n} + β {(\frac{1 - i \sqrt{3}}{2})}^{n}

,

gdzie $α$ oraz $β$ są liczbami zespolonymi. Mając podane wyrazy $a_{0}$ oraz $a_{1}$ możemy wyliczyć $α$ oraz $β$ z następującego układu równań:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{align} 0&=\alpha\cdot1+\beta\cdot1,\\ 1&=\alpha\cdot\frac{1+i\sqrt{3}}{2}+\beta\cdot\frac{1-i\sqrt{3}}{2}. \end{align} \right}

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

a_{n} = - \frac{i \sqrt{3}}{3} {(\frac{1 + i \sqrt{3}}{2})}^{n} + \frac{i \sqrt{3}}{3} {(\frac{1 - i \sqrt{3}}{2})}^{n}

,

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

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

,

uzyskujemy

a_{n} = - \frac{i \sqrt{3}}{3} {(\frac{1 + i \sqrt{3}}{2})}^{n mod 6} + \frac{i \sqrt{3}}{3} {(\frac{1 - i \sqrt{3}}{2})}^{n mod 6}

Widzimy więc, że ciąg o wyrazach $a_{n} = a_{n mod 6}$ 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

| a_{n} | \leq 1

dla

n = 0, 1, 2, 3, \dots

Ćwiczenie 7

Rozwiąż równanie rekurencyjne postaci

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{align} a_0&=1,\\ a_1&=5,\\ a_2&=11,\\ a_n&=3a_{n-1}+2a_{n-2}-2a_{n-3}\quad\text{dla}\ n\geq3. \end{align} \right}

Wskazówka

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

Rozwiązanie

Niech $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ . Po podstawieniu równości z równania rekurencyjnego otrzymujemy:

\begin{aligned} \sum_{n = 0}^{\infty} a_{n} x^{n} & = 1 + 5 x + 11 x^{2} + 3 x \sum_{n = 2}^{\infty} a_{n} x^{n} + 2 x^{2} \sum_{n = 1}^{\infty} a_{n} x^{n} - 2 x^{3} \sum_{n = 0}^{\infty} a_{n} x^{n} \\ = 1 + 2 x - 6 x^{2} + 3 x \sum_{n = 0}^{\infty} a_{n} x^{n} + 2 x^{2} \sum_{n = 0}^{\infty} a_{n} x^{n} - 2 x^{3} \sum_{n = 0}^{\infty} a_{n} x^{n} . \end{aligned}

W miejsce $\sum_{n = 0}^{\infty} a_{n} x^{n}$ wstawiamy $A (x)$ i otrzymujemy:

A (x) = 1 + 2 x - 6 x^{2} + 3 x A (x) + 2 x^{2} A (x) - 2 x^{3} A (x)

Otrzymane równanie przekształcamy do postaci

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

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

\sum_{n = 0}^{\infty} a_{n} x^{n} = \sum_{n = 0}^{\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$ .

@@ Linia 22: / Linia 22: @@
 {{wzor|1|1|
 <math>
-\frac{1}{1-x}=1+x+x^2+x^3+x^4+\ldots.
+\frac{1}{1-x}=1+x+x^2+x^3+x^4+\ldots</math>}}
-</math>}}
 ; ad a. Dla funkcji tworzącej  <math>A\!\left( x \right)=a_0+a_1x+a_2x^2+a_3x^3+\ldots</math>, korzystając z ([[#1|1]]), otrzymujemy równość:
-<center><math>A\!\left( x \right)=1+2x+2^2x^2+2^3x^3+\ldots=\frac{1}{1-2x}.
+<center><math>A\!\left( x \right)=1+2x+2^2x^2+2^3x^3+\ldots=\frac{1}{1-2x}</math></center>
-</math></center>
@@ Linia 237: / Linia 235: @@
 -6&=\left( -2-\sqrt{2} \right)A+\left( -2+\sqrt{2} \right)B+2C
 \end{align}
-\right.
+\right</math></center>
-</math></center>
@@ Linia 281: / Linia 278: @@
 a_n&=2a_{n-1}-a_{n-2},\quad\text{dla}\ n\geq2.
 \end{align}
-\right.
+\right</math></center>
-</math></center>
 }}
@@ Linia 299: / Linia 295: @@
-<center><math>1-2x+x^2=\left( 1-x \right)^2.
+<center><math>1-2x+x^2=\left( 1-x \right)^2</math></center>
-</math></center>
@@ Linia 306: / Linia 301: @@
-<center><math>a_n = \left( \alpha n+\beta \right)1^n,
+<center><math>a_n = \left( \alpha n+\beta \right)1^n</math>,</center>
-</math></center>
@@ Linia 320: / Linia 314: @@
 &=\alpha\cdot1+\beta.
 \end{align}
-\right.
+\right</math></center>
-</math></center>
@@ Linia 327: / Linia 320: @@
-<center><math>a_n=n,
+<center><math>a_n=n</math>,</center>
-</math></center>
@@ Linia 344: / Linia 336: @@
 a_n&=a_{n-1}-a_{n-2}\quad\text{dla}\ n\geq2.
 \end{align}
-\right.
+\right</math></center>
-</math></center>
@@ Linia 364: / Linia 355: @@
-<center><math>1-x+x^2=\left( 1-\frac{1+i\sqrt{3}}{2}x \right)\left( 1-\frac{1-i\sqrt{3}}{2}x \right).
+<center><math>1-x+x^2=\left( 1-\frac{1+i\sqrt{3}}{2}x \right)\left( 1-\frac{1-i\sqrt{3}}{2}x \right)</math></center>
-</math></center>
@@ Linia 373: / Linia 363: @@
 <center><math>a_n = \alpha\left( \frac{1+i\sqrt{3}}{2} \right)^n+
-\beta\left( \frac{1-i\sqrt{3}}{2} \right)^n,
+\beta\left( \frac{1-i\sqrt{3}}{2} \right)^n</math>,</center>
-</math></center>
@@ Linia 387: / Linia 376: @@
 &=\alpha\cdot\frac{1+i\sqrt{3}}{2}+\beta\cdot\frac{1-i\sqrt{3}}{2}.
 \end{align}
-\right.
+\right</math></center>
-</math></center>
@@ Linia 395: / Linia 383: @@
 <center><math>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,
+\frac{i\sqrt{3}}{3}\left( \frac{1-i\sqrt{3}}{2} \right)^n</math>,</center>
-</math></center>
@@ Linia 402: / Linia 389: @@
-<center><math>\left( \frac{1+i\sqrt{3}}{2} \right)^6=1,\quad\left( \frac{1-i\sqrt{3}}{2} \right)^6=1,
+<center><math>\left( \frac{1+i\sqrt{3}}{2} \right)^6=1,\quad\left( \frac{1-i\sqrt{3}}{2} \right)^6=1</math>,</center>
-</math></center>
@@ Linia 409: / Linia 395: @@
-<center><math>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}.
+<center><math>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}</math></center>
-</math></center>
@@ Linia 418: / Linia 403: @@
-<center><math>a_0=0,\quad a_1=1,\quad a_2=1,\quad a_3=0,\quad a_4=-1,\quad a_5=-1.
+<center><math>a_0=0,\quad a_1=1,\quad a_2=1,\quad a_3=0,\quad a_4=-1,\quad a_5=-1</math></center>
-</math></center>
@@ Linia 426: / Linia 410: @@
-<center><math>\left\vert a_n \right\vert\leq 1\quad</math> dla <math>\ n=0,1,2,3,\ldots.
+<center><math>\left\vert a_n \right\vert\leq 1\quad</math> dla <math>\ n=0,1,2,3,\ldots</math></center>
-</math></center>
@@ Linia 443: / Linia 426: @@
 a_n&=3a_{n-1}+2a_{n-2}-2a_{n-3}\quad\text{dla}\ n\geq3.
 \end{align}
-\right.
+\right</math></center>
-</math></center>
@@ Linia 469: / Linia 451: @@
-<center><math>A\!\left( x \right)= 1+2x-6x^2 +3xA\!\left( x \right)+2x^2A\!\left( x \right)-2x^3A\!\left( x \right).
+<center><math>A\!\left( x \right)= 1+2x-6x^2 +3xA\!\left( x \right)+2x^2A\!\left( x \right)-2x^3A\!\left( x \right)</math></center>
-</math></center>
@@ Linia 476: / Linia 457: @@
-<center><math>A\!\left( x \right)=\frac{1+2x-6x^2}{1-3x-2x^2+2x^3}.
+<center><math>A\!\left( x \right)=\frac{1+2x-6x^2}{1-3x-2x^2+2x^3}</math></center>
-</math></center>
@@ Linia 483: / Linia 463: @@
-<center><math>\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.
+<center><math>\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</math></center>
-</math></center>

Matematyka dyskretna 1/Ćwiczenia 7: Funkcje tworzące: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:47, 11 wrz 2023

Funkcje tworzące

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia