Rozwiązać równanie rekurencyjne używając funkcji tworzących

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Browning0
Użytkownik
Użytkownik
Posty: 333
Rejestracja: 2 lis 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 82 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: Browning0 »

Witajcie, mam takie zadanie i w sumie umiem je zrobić tylko do połowy, a w sumie nie wiem nawet czy tę połowę robię dobrze...

Treść zadania brzmi:
Rozwiązać równanie rekurencyjne przy pomocy funkcji tworzących
\(\displaystyle{ a_n = 4a_{n-1} - 4a_{n-2} - 3^{n-2} \quad a_0=a_1=1}\)
No to jazda!

\(\displaystyle{ A(x) = \sum_{n=0}^{\infty} a_nx^n = 1 + x + \sum_{n=2}^{\infty} (4a_{n-1}-4a_{n-2}-3^{n-2})x^n = \\ \\ = 1 + x + 4 \sum_{n=2}^{\infty} a_{n-1}x^n - 4 \sum_{n=2}^{\infty} a_{n-2}x^n - \sum_{n=2}^{\infty}3^{n-2}x^n = \\ \\ = 1 + x + 4x \sum_{n=1}^{\infty}a_n x^n - 4x^2\sum_{n=0}^{\infty}a_n x^n - x^2\sum_{n=0}^{\infty}3^n x^n = \\ \\ = 1 + x + 4x (A(x) - 1) -4x^2 A(x) - \frac{x^2}{1-3x}}\)

Czyli:
\(\displaystyle{ A(x) = 1 + x + 4xA(x) - 4x -4x^2 A(x) - \frac{x^2}{1-3x} \\ \\ A(x)(1 - 4x + 4x^2) = 1 - 3x - \frac{x^2}{1-3x} \\ \\ A(x) = \frac{1-3x}{1-4x+4x^2} - \frac{x^2}{(1-3x)(1-4x+4x^2)}}\)

No właśnie... I co dalej trzeba z tym zrobić? ;/ Bardzo proszę o wskazówki!
Ostatnio zmieniony 3 cze 2012, o 18:50 przez Browning0, łącznie zmieniany 1 raz.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: »

Browning0 pisze:
Rozwiązać równanie rekurencyjne przy pomocy funkcji tworzących
\(\displaystyle{ a_n = 4a_{n-1} - 4a_{n-2} - 3^{n-2} \quad a_0=a_1=a}\)
\(\displaystyle{ A(x) = \sum_{n=0}^{\infty} a_nx^n = 1 + 1 + \sum_{n=2}^{\infty} (4a_{n-1}-4a_{n-2}-3^{n-2})x^n}\)
Nawet jeśli w treści zadania zrobiłeś literówkę i ma być \(\displaystyle{ a_0=a_1=1}\), to i tak powinno być:
\(\displaystyle{ A(x) = \sum_{n=0}^{\infty} a_nx^n = 1 + x + \sum_{n=2}^{\infty} (4a_{n-1}-4a_{n-2}-3^{n-2})x^n}\)

A po prawidłowym wyznaczeniu funkcji tworzącej należy rozłożyć ją na ułamki proste.

Q.
Browning0
Użytkownik
Użytkownik
Posty: 333
Rejestracja: 2 lis 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 82 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: Browning0 »

Święta prawda! Już poprawiłem żeby nie mylić innych.

No to mamy:
\(\displaystyle{ A(x) = \frac{1-3x}{1-4x+4x^2} - \frac{x^2}{(1-3x)(1-4x+4x^2)} = \frac{1-3x}{(2x-1)^2} + \frac{x^2}{(3x-1)(2x-1)^2}}\)

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

Z tego wynika, że:
\(\displaystyle{ A(x) =\frac{1}{3x-1} - \frac{2}{2x-1}}\)

Dobra, zaczyna wyglądać nawet ładnie, bo wcześniej wychodził "kartofel" ^^
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: »

Zgadza się, ale wygodniej zapisać to w postaci:

\(\displaystyle{ A(x)=\frac{2}{1-2x}-\frac{1}{1-3x}}\)

i teraz korzystając ze wzoru \(\displaystyle{ \sum_{n=0}^{\infty}q^n= \frac{1}{1-q}}\) rozwinąć w szereg. Z definicji funkcji tworzącej to co będzie stało przy \(\displaystyle{ x^n}\) to będzie właśnie \(\displaystyle{ a_n}\).

Q.
Browning0
Użytkownik
Użytkownik
Posty: 333
Rejestracja: 2 lis 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 82 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: Browning0 »

\(\displaystyle{ \sum_{n=0}^{\infty} (2^{(n+1)} - 3^n)x^n}\)

Dziękuję bardzo za pomoc! Pozdrawiam
Awatar użytkownika
johanneskate
Użytkownik
Użytkownik
Posty: 488
Rejestracja: 24 lut 2009, o 18:00
Płeć: Mężczyzna
Podziękował: 38 razy
Pomógł: 2 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: johanneskate »

Rozwiązywałem podobne zadanie i natrafiłem przy A(x) na następujący składnik:
\(\displaystyle{ \frac{1}{(1-2x)^{2}}}\). Jak rozwinąć to w szereg?
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: adambak »

znane: \(\displaystyle{ \frac{1}{(1-ax)^k} = \sum_{n=0}^{+\infty} {n+k-1 \choose k-1} (ax)^n}\)
iridescent
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 25 paź 2015, o 11:10
Płeć: Kobieta
Lokalizacja: Warszawa

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: iridescent »

Mocno odkopuję temat, ale w jaki sposób zostało rozłożone
\(\displaystyle{ \frac{1-3x}{(2x-1)^2}}\) oraz \(\displaystyle{ \frac{x^2}{(3x-1)(2x-1)^2}}\)
Dlaczego akurat takie mianowniki i jak zostały policzone liczniki?
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: Kartezjusz »

Tak jak przy całkach. Mianowniki były czynnikami postaci iloczynowej
iridescent
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 25 paź 2015, o 11:10
Płeć: Kobieta
Lokalizacja: Warszawa

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: iridescent »

A istnieje na to pytanie odpowiedź dla kogoś kogo jeszcze całki nie obowiązują, a funkcje tworzące tak?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: arek1357 »

Istnieje odpowiedź
iridescent
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 25 paź 2015, o 11:10
Płeć: Kobieta
Lokalizacja: Warszawa

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: iridescent »

Niesamowicie pomocne, dziękuję.
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Rozwiązać równanie rekurencyjne używając funkcji tworzących

Post autor: Mariusz M »

iridescent, tutaj nie chodzi o całki tylko sumę szeregu geometrycznego i jego pochodnych
(pochodne chyba już wróciły na rozszerzoną, za moich czasów były w minimum programowym)

Jeżeli funkcję tworzącą przedstawisz w postaci sumy ułamków postaci

\(\displaystyle{ \frac{A_{km}}{\left( 1-\lambda_{m}x\right)^{k} }}\)

to łatwiej ci będzie zwinąć funkcję w szereg będący sumą szeregów geometrycznych i jego pochodnych

Pochodne i tak ci się przydadzą bo co jeśli funkcja tworząca nie będzie wymierna ?
Jak wtedy uzyskasz współczynniki ?
ODPOWIEDZ