Rozwiąż rekurencję z wykorzystaniem funkcji tworzącej:
\(\displaystyle{ \begin{cases} g_{0}=1 \\ g _{n}= g_{n-1}+ 2g_{n-2}+...+n \cdot g _{0}+n+1 , n \ge 1\end{cases}}\)
Wydaje mi się, że ułożyłem dobrze uniwersalną tożsamość rekurencyjną, mianowicie:
\(\displaystyle{ g_{n}= g_{n-1}+ g_{n-2}+...+n \cdot g_{0}+n+1-(2n+1)w(n \le 0)}\) gdzie w jest wartością logiczną zdania.
Oznaczam funkcje tworzącą \(\displaystyle{ G(z)= \sum_{n}^{} g_{n} z ^{n}}\) i podstawiam do tożsamości wyżej ale dalej pojawiają sie schody...
Rozwiązywanie rekurencji z wykorzystaniem funkcji tworzących
-
Bartom
- Użytkownik
- Posty: 67
- Rejestracja: 5 gru 2015, o 12:39
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 21 razy
Rozwiązywanie rekurencji z wykorzystaniem funkcji tworzących
Ostatnio zmieniony 22 cze 2017, o 21:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Rozwiązywanie rekurencji z wykorzystaniem funkcji tworzących
No, jeśli \(\displaystyle{ G(z)= \sum_{n=0}^{ \infty }g_n z^n}\), to
\(\displaystyle{ G(z)=g_0+ \sum_{n=1}^{ \infty }\left( n+1+ \sum_{k=0}^{n-1}(n-k)g_k \right)z^n=\\=g_0+ \sum_{n=1}^{ \infty }(n+1)z^n+ \sum_{n=1}^{ \infty } \sum_{k=0}^{n-1}(n-k)g_k z^n=\\=1+\left( \sum_{n=1}^{ \infty }z^{n+1} \right)'+\sum_{n=1}^{ \infty } \sum_{k=0}^{n-1}g_k z^k \cdot (n-k)z^{n-k}}\)
Przyjrzyjmy się tej ostatniej, wewnętrznej sumie. Łatwo widać, że
\(\displaystyle{ \sum_{k=0}^{n-1}g_k z^k \cdot (n-k)z^{n-k}= z^n\sum_{k=0}^{n}g_k \cdot (n-k)}\)
- po prostu dodaliśmy rozpisane zero.
Teraz zastosujemy taki fakt: funkcja tworząca splotu dwóch ciągów to iloczyn ich funkcji tworzących.
Zauważmy, że \(\displaystyle{ \sum_{k=0}^{n}g_k \cdot (n-k)}\)
to splot ciągów \(\displaystyle{ (g_n)_{n \in \NN}}\) i \(\displaystyle{ (n)_{n \in \NN}}\)
Zatem funkcja tworząca splotu:
\(\displaystyle{ \sum_{n=0}^{ \infty } \sum_{k=0}^{n}g_k z^k \cdot (n-k)z^{n-k}=G(z) \cdot \frac{z}{(1-z)^2}}\)
gdyż funkcja tworząca \(\displaystyle{ (n)}\):
\(\displaystyle{ \sum_{n=0}^{ \infty }n z^n= \frac{z}{(1-z)^2}}\)
(znane, można skorzystać z różniczkowania/całkowania szeregów potęgowych wyraz po wyrazie).
Ponadto oczywiście mamy
\(\displaystyle{ \left( \sum_{n=1}^{ \infty }z^{n+1} \right)'=\left( \frac{z^2}{1-z} \right)'= \frac{2z-z^2}{(1-z)^2}}\)
Czyli finalnie otrzymujemy równość:
\(\displaystyle{ G(z)=1+ \frac{2z-z^2}{(1-z)^2}+G(z) \frac{z}{(1-z)^2}}\)
- stąd wyliczamy \(\displaystyle{ G(z)}\), mnie wyszło
\(\displaystyle{ G(z)= \frac{1}{z^2-3z+1}}\) (ale lepiej to sprawdź, bo nie umiem liczyć).
To rozkładasz na ułamki proste (trochę brzydkie), rozwijasz w szeregi potęgowe ze wzoru na sumę szeregu geometrycznego (tylko niejako w drugą stronę ten wzór stosujesz)
i patrzysz na to, co stoi przy \(\displaystyle{ z^n}\).
\(\displaystyle{ G(z)=g_0+ \sum_{n=1}^{ \infty }\left( n+1+ \sum_{k=0}^{n-1}(n-k)g_k \right)z^n=\\=g_0+ \sum_{n=1}^{ \infty }(n+1)z^n+ \sum_{n=1}^{ \infty } \sum_{k=0}^{n-1}(n-k)g_k z^n=\\=1+\left( \sum_{n=1}^{ \infty }z^{n+1} \right)'+\sum_{n=1}^{ \infty } \sum_{k=0}^{n-1}g_k z^k \cdot (n-k)z^{n-k}}\)
Przyjrzyjmy się tej ostatniej, wewnętrznej sumie. Łatwo widać, że
\(\displaystyle{ \sum_{k=0}^{n-1}g_k z^k \cdot (n-k)z^{n-k}= z^n\sum_{k=0}^{n}g_k \cdot (n-k)}\)
- po prostu dodaliśmy rozpisane zero.
Teraz zastosujemy taki fakt: funkcja tworząca splotu dwóch ciągów to iloczyn ich funkcji tworzących.
Zauważmy, że \(\displaystyle{ \sum_{k=0}^{n}g_k \cdot (n-k)}\)
to splot ciągów \(\displaystyle{ (g_n)_{n \in \NN}}\) i \(\displaystyle{ (n)_{n \in \NN}}\)
Zatem funkcja tworząca splotu:
\(\displaystyle{ \sum_{n=0}^{ \infty } \sum_{k=0}^{n}g_k z^k \cdot (n-k)z^{n-k}=G(z) \cdot \frac{z}{(1-z)^2}}\)
gdyż funkcja tworząca \(\displaystyle{ (n)}\):
\(\displaystyle{ \sum_{n=0}^{ \infty }n z^n= \frac{z}{(1-z)^2}}\)
(znane, można skorzystać z różniczkowania/całkowania szeregów potęgowych wyraz po wyrazie).
Ponadto oczywiście mamy
\(\displaystyle{ \left( \sum_{n=1}^{ \infty }z^{n+1} \right)'=\left( \frac{z^2}{1-z} \right)'= \frac{2z-z^2}{(1-z)^2}}\)
Czyli finalnie otrzymujemy równość:
\(\displaystyle{ G(z)=1+ \frac{2z-z^2}{(1-z)^2}+G(z) \frac{z}{(1-z)^2}}\)
- stąd wyliczamy \(\displaystyle{ G(z)}\), mnie wyszło
\(\displaystyle{ G(z)= \frac{1}{z^2-3z+1}}\) (ale lepiej to sprawdź, bo nie umiem liczyć).
To rozkładasz na ułamki proste (trochę brzydkie), rozwijasz w szeregi potęgowe ze wzoru na sumę szeregu geometrycznego (tylko niejako w drugą stronę ten wzór stosujesz)
i patrzysz na to, co stoi przy \(\displaystyle{ z^n}\).