Funkcja tworząca - równanie rekurencyjne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
pg2464
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 26 lut 2014, o 23:39
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 11 razy

Funkcja tworząca - równanie rekurencyjne

Post autor: pg2464 »

Witam, w rozwiązaniu funkcji rekurencyjnej nie rozumiem ostatniego przejscia, czy byłby ktoś wstanie mi to wytłumaczyć

Po rozkładzie na ułamki proste otrzymałem
\(\displaystyle{ A(z)= \frac{z ^{2} }{(1-z) ^{2}(1+z) }= \frac{- \frac{1}{4} }{1-z}+ \frac{ \frac{1}{2} }{(1-z) ^{2} } + \frac{ -\frac{1}{4} }{1+z}}\)

następnie było co takiego:
\(\displaystyle{ A(z)= \sum_{n \ge 0}^{}(- \frac{1}{4}+ \frac{1}{2}(n+1)- \frac{1}{4}(-1) ^{n} )z ^{n}}\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Funkcja tworząca - równanie rekurencyjne

Post autor: Premislav »

Wykorzystano wzór na sumę szeregu geometrycznego (dwukrotnie) i fakt, że wewnątrz koła zbieżności szeregi potęgowe można różniczkować wyraz po wyrazie.

Ze wzoru na sumę szeregu geometrycznego mamy tamto
\(\displaystyle{ \frac{- \frac{1}{4} }{1-z}= \sum_{n=0}^{ \infty } -\frac 1 4z^{n}}\)
oraz
\(\displaystyle{ \frac{ -\frac{1}{4} }{1+z}= \frac{ -\frac{1}{4} }{1-(-z)}= \sum_{n=0}^{+\infty} - \frac{1}{4}(-z)^{n}= \sum_{n=0}^{+\infty} - \frac{1}{4}(-1)^{n}z^{n}}\),
zaś ze zróżniczkowania stronami po \(\displaystyle{ z}\) tożsamości
\(\displaystyle{ \frac{ \frac{1}{2} }{1-z} = \sum_{n=0}^{+\infty} \frac{1}{2} z^{n}}\)
(przy czym ten szereg różniczkujemy wyraz po wyrazie)
wynika \(\displaystyle{ \frac{ \frac{1}{2} }{(1-z) ^{2} } = \sum_{n=1}^{+\infty} \frac{n}{2}z^{n-1}= \sum_{n=0}^{+\infty} \frac{1}{2}(n+1)z^{n}}\)
pg2464
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 26 lut 2014, o 23:39
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 11 razy

Funkcja tworząca - równanie rekurencyjne

Post autor: pg2464 »

dzięki, to już rozumiem, ale teraz przy innym równaniu trafiłem znów na problem.

oto równanie
\(\displaystyle{ a_{0}=2}\)
\(\displaystyle{ a _{1}=3}\)
\(\displaystyle{ a_{2}=5}\)
\(\displaystyle{ a_{n+3}=7a _{n+2} -16a _{n+1}+12a _{n}}\)
\(\displaystyle{ m=n+3}\)

\(\displaystyle{ A(z)= \frac{1 +3z +5z^{2}}{1 - 7z +16z^{2}-12^{3}}}\)

Po rozkładzie na ułamki proste
\(\displaystyle{ A(z)= \frac{ \frac{41}{4} }{x - \frac{1}{2} } + \frac{ \frac{-19}{8} }{(x - \frac{1}{2} )^{2}} + \frac{ \frac{32}{3} }{x- \frac{1}{3} }= \frac{41}{2(2x-1)}- \frac{19}{2(2x-1)^{2}}- \frac{32}{3x-1}}\)

i tu jest problem bo wynik jest postaci
\(\displaystyle{ a _{n}= \frac{1}{ \sqrt{5} }(( \frac{1+ \sqrt{5} }{2} ) ^{n+3} )-(\frac{1- \sqrt{5} }{2} ) ^{n+3})}\))
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Funkcja tworząca - równanie rekurencyjne

Post autor: Premislav »

To dziwne, bo mnie wychodzi \(\displaystyle{ A(z)= \frac{16z^{2}-11z+2}{1-7z+16z^{2}-12z^{3}}}\). Wprawdzie liczyć nie umiem, ale sprawdzałem to trzy razy.

-- 8 cze 2016, o 11:08 --

Chociaż gdy się nie umie liczyć, to można sprawdzać i 500 razy.-- 8 cze 2016, o 11:20 --W każdym razie pomijając Twoje czy moje błędy rachunkowe, sposób postępowania jest taki sam, jak poprzednio, ogólnie dla odpowiednich \(\displaystyle{ a,x,b}\) masz:

\(\displaystyle{ \frac{1}{ax+b}= \frac{1}{b} \frac{1}{1+ \frac{a}{b}x }= \frac{1}{b} \sum_{n=0}^{+\infty} \left( -\frac{ax}{b}\right)^{n}}\)
\(\displaystyle{ b\neq 0, \left| \frac{ax}{b} \right| <1}\), chyba tyle.
Po zróżniczkowaniu tego stronami mamy...
pg2464
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 26 lut 2014, o 23:39
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 11 razy

Funkcja tworząca - równanie rekurencyjne

Post autor: pg2464 »

pg2464 pisze: i tu jest problem bo wynik jest postaci
\(\displaystyle{ a _{n}= \frac{1}{ \sqrt{5} }(( \frac{1+ \sqrt{5} }{2} ) ^{n+3} )-(\frac{1- \sqrt{5} }{2} ) ^{n+3})}\))

nie wiem czy gdzieś popełniam błędy rachunkowe , ale zarówno dla mojej jak i Twojej wersji nie wychodzi mi powyższy wynik, chyba że jest to alternatywna forma rozwiązania


to chyba błąd w opowiedziach, chyba powinno być
\(\displaystyle{ (n-1)2 ^{n}+3 ^{n}}\) ?
i wtedy chyba Twoje rozwiązanie byłoby bliższe ?
Ostatnio zmieniony 8 cze 2016, o 15:03 przez pg2464, łącznie zmieniany 1 raz.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Funkcja tworząca - równanie rekurencyjne

Post autor: Premislav »

Ja nie rozumiem, skąd się bierze to rozwiązanie. Być może zastosowano równanie charakterystyczne.
Wybacz, ale mam ciekawsze rzeczy do roboty niż sprawdzanie po pięć razy obliczeń, może ktoś inny coś poradzi.
pg2464
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 26 lut 2014, o 23:39
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 11 razy

Funkcja tworząca - równanie rekurencyjne

Post autor: pg2464 »

dzięki za pomoc, może dalej coś wykombinuję
ODPOWIEDZ