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

Funkcje tworzące

Ćwiczenie ex some genereiting function

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 .

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 (Uzupelnic eq genfunc 1,1,1,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 twierdzenia [con][con newton for integer] otrzymamy:

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

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 ex exponential(x)

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 ex newton for integer

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 [th][thm (1+x){}y] 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ć:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

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

Ćwiczenie ex wymierna

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $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}{rcl} 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{array}

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 ex recurence 1

Rozwiąż równanie rekurencyjne:

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

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{array}{rcl} 0 & = α \cdot 0 + β, \\ 1 & = α \cdot 1 + β . \end{array}

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

a_{n} = n,

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

Ćwiczenie ex cyclic recurence

Rozwiąż równanie rekurencyjne postaci

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

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{array}{rcl} 0 & = α \cdot 1 + β \cdot 1, \\ 1 & = α \cdot \frac{1 + i \sqrt{3}}{2} + β \cdot \frac{1 - i \sqrt{3}}{2} . \end{array}

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 ex recurence 2

Rozwiąż równanie rekurencyjne postaci

{\begin{array}{rcl} 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{array}

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $\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 Uzupelnic ex wymierna| 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$ .

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

Funkcje tworzące

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia