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

← poprzednia edycja następna edycja →

WizualnieWikikod

Wersja z 13:19, 5 cze 2020

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

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

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:

{\begin{aligned} a_{0} & = 0, \\ a_{1} & = 1, \\ a_{n} & = 2 a_{n - 1} - a_{n - 2}, dla n \geq 2 . \end{aligned}

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

{\begin{aligned} 0 & = α \cdot 0 + β, \\ 1 & = α \cdot 1 + β . \end{aligned}

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

{\begin{aligned} a_{0} & = 0, \\ a_{1} & = 1, \\ a_{n} & = a_{n - 1} - a_{n - 2} dla n \geq 2 . \end{aligned}

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

{\begin{aligned} 0 & = α \cdot 1 + β \cdot 1, \\ 1 & = α \cdot \frac{1 + i \sqrt{3}}{2} + β \cdot \frac{1 - i \sqrt{3}}{2} . \end{aligned}

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

{\begin{aligned} a_{0} & = 1, \\ a_{1} & = 5, \\ a_{2} & = 11, \\ a_{n} & = 3 a_{n - 1} + 2 a_{n - 2} - 2 a_{n - 3} dla n \geq 3 . \end{aligned}

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 154: / Linia 154: @@
-<center><math>\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\ =\\
+<center><math>\displaystyle \begin{align} &&\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</math></center>
+\end{align}</math></center>
@@ Linia 216: / Linia 216: @@
-<center><math>\displaystyle \aligned 1+2x-6x^2&=
+<center><math>\displaystyle \begin{align} 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)\\
@@ Linia 222: / Linia 222: @@
 &=\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</math></center>
+\end{align}</math></center>
@@ Linia 232: / Linia 232: @@
 <center><math>\displaystyle \left\lbrace
-\aligned
+\begin{align}
 &=A+B+C\\
 &=\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
+\end{align}
 \right.
 </math></center>
@@ Linia 276: / Linia 276: @@
 <center><math>\displaystyle \left\lbrace
-\aligned
+\begin{align}
 a_0&=0,\\
 a_1&=1,\\
 a_n&=2a_{n-1}-a_{n-2},\quad\textrm{dla}\ n\geq2.
-\endaligned
+\end{align}
 \right.
 </math></center>
@@ Linia 316: / Linia 316: @@
 <center><math>\displaystyle \left\lbrace
-\aligned
+\begin{align}
 &=\alpha\cdot0+\beta,\\
 &=\alpha\cdot1+\beta.
-\endaligned
+\end{align}
 \right.
 </math></center>
@@ Linia 339: / Linia 339: @@
 <center><math>\displaystyle \left\lbrace
-\aligned
+\begin{align}
 a_0&=0,\\
 a_1&=1,\\
 a_n&=a_{n-1}-a_{n-2}\quad\textrm{dla}\ n\geq2.
-\endaligned
+\end{align}
 \right.
 </math></center>
@@ Linia 383: / Linia 383: @@
 <center><math>\displaystyle \left\lbrace
-\aligned
+\begin{align}
 &=\alpha\cdot1+\beta\cdot1,\\
 &=\alpha\cdot\frac{1+i\sqrt{3}}{2}+\beta\cdot\frac{1-i\sqrt{3}}{2}.
-\endaligned
+\end{align}
 \right.
 </math></center>
@@ Linia 437: / Linia 437: @@
 <center><math>\displaystyle \left\lbrace
-\aligned
+\begin{align}
 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
+\end{align}
 \right.
 </math></center>
@@ Linia 461: / Linia 461: @@
-<center><math>\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\\
+<center><math>\displaystyle \begin{align} \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</math></center>
+\end{align}</math></center>

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

Wersja z 13:19, 5 cze 2020

Funkcje tworzące

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia