Funkcja tworząca i postać jawna ciągu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Funkcja tworząca i postać jawna ciągu

Post autor: PAV38 » 10 sie 2011, o 16:03

Mam funkcję tworzącą:
\(\displaystyle{ A(x)= \frac{1}{(1-x)^{2}}}\)

Należy znaleźć odpowiadający jej ciąg i podać jego postać jawną.
Wcześniej trafiałem na przykłady, gdzie ten ciągu było widać prawie od razu, albo dawało się rozbić ułamek na dwa ułamki proste, z który dostawałem gotowe sumy. Ten przykład jest trochę dziwny ;/

Mój tok rozumowania:
\(\displaystyle{ A(x)=\frac{1}{(1-x)^{2}}=\frac{1}{x^{2}-2x+1}}\)

A funkcje tworzące w podobnej postaci, mają ciągi zdefiniowane rekurencyjnie np. ciąg Fibbonaciego itd.

Dlatego rozwiązałem taki przykład "od tyłu". Metodą zgadywania doszedłem, do tego, że taki ciąg powinien mieć taką postać:

\(\displaystyle{ \begin{cases} a_{0}=1 \\ a_{1}=0 \\ a_{n}=2a_{n-1}-a_{n-2} \end{cases}}\)

I teraz rozwiązując go:
\(\displaystyle{ A(x)= \sum_{n=0}^{+ \infty } a_{n} x^{n}= 1+\sum_{n=2}^{+ \infty } a_{n} x^{n}=1+\sum_{n=2}^{+ \infty } 2a_{n-1}-a_{n-2} x^{n}=1+2\sum_{n=2}^{+ \infty } a_{n-1}-\sum_{n=2}^{+ \infty }a_{n-2} x^{n}=1+2\sum_{n=2}^{+ \infty } a_{n-1}x^{n}-\sum_{n=2}^{+ \infty }a_{n-2} x^{n}=1+2x\sum_{n=1}^{+ \infty } a_{n}x^{n}-x^{2}\sum_{n=0}^{+ \infty }a_{n} x^{n}=1+2xA(x)-x^{2}A(x)}\)

\(\displaystyle{ A(x)=1+2xA(x)-x^{2}A(x)}\)

\(\displaystyle{ A(x)-2xA(x)+x^{2}A(x)=1}\)

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

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

I zakładając, że ta koncepcja jest w ogóle dobra, rozwiązuję zwykłą rekurencję:

\(\displaystyle{ \begin{cases} a_{0}=1 \\ a_{1}=0 \\ a_{n}=2a_{n-1}-a_{n-2} \end{cases}}\)

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

\(\displaystyle{ x_{0}=1}\)

\(\displaystyle{ a_{n}=c_{1}(1)^{n}+c_{2}n(1)^{n}}\)

\(\displaystyle{ \begin{cases} c_{1}=1 \\ c_{1}+c_{2}=0 \end{cases}}\)

\(\displaystyle{ \begin{cases} c_{1}=1 \\ c_{2}=-1 \end{cases}}\)

A zatem postać jawna ciągu zdefiniowanego rekurencyjnie to:
\(\displaystyle{ a_{n}=(1)^{n}-n(1)^{n}}\)

Czy przykład jest dobrze rozwiązany? Jeśli nie, to jak trzeba go zrobić?

janusz47
Użytkownik
Użytkownik
Posty: 6320
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 13 razy
Pomógł: 1362 razy

Funkcja tworząca i postać jawna ciągu

Post autor: janusz47 » 10 sie 2011, o 16:16

Rozwiązanie tego przykładu "od przodu".
1) Zapisać funkcję tworzącą w postaci sumy dwóch ułamków prostych.
2) Każdemu z ułamków przyporządkować odpowiadający mu nieskończony szereg geometryczny.
3) Zsumować ( zapisać w postaci jednej sumy) szeregi.
4) Odczytać \(\displaystyle{ a_{n}}\) z szeregu , który jest sumą tych dwóch szeregów.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Funkcja tworząca i postać jawna ciągu

Post autor: PAV38 » 10 sie 2011, o 16:25

A mogę prosić o sprawdzenie poprawności mojego rozwiązania??

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Funkcja tworząca i postać jawna ciągu

Post autor: » 10 sie 2011, o 16:30

Twoje rozwiązanie jest błędne chociażby dlatego, że prawidłowa odpowiedź to \(\displaystyle{ n+1}\). Poza tym metoda jest raczej nieefektywna.

Ja bym proponował zacząć od zróżniczkowania stronami równości:
\(\displaystyle{ \frac{1}{1-x}= \sum_{n=0}^{\infty}x^n}\)

Q.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Funkcja tworząca i postać jawna ciągu

Post autor: PAV38 » 10 sie 2011, o 16:48

No tak, w sumie faktycznie tak się da

Zastanawia mnie gdzie, robię błąd w obliczeniach z pierwszego postu. Bo wynik jest już prawie dobry. Czyli pewnie błąd leży w obliczeniach.

Przepraszam, że męczę jakąś skomplikowaną metodę, ale jest dla mnie po prostu chyba najlepiej zrozumiała Jakby udało się komuś wyłapać błąd, to będę bardzo wdzięczny

janusz47
Użytkownik
Użytkownik
Posty: 6320
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 13 razy
Pomógł: 1362 razy

Funkcja tworząca i postać jawna ciągu

Post autor: janusz47 » 10 sie 2011, o 17:03

Proponuję zapisać funkcję tworzącą w postaci sumy dwóch szeregów lub jak proponuje Kol.Qń zróżniczkować stronami równość na sumę nieskończonego szeregu geometrycznego.
\(\displaystyle{ \frac{1}{1-x} = \sum_{n=0}^{\infty}x^{n}.}\)
\(\displaystyle{ \frac{1}{(1-x)^2} = \sum_{k=1}^{\infty}kx^{k-1}|_{k-1 = n} = \sum_{n=0}^{\infty}(n+1)x^{n}.}\)
Stąd
\(\displaystyle{ a_{n} = n+1.}\)

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Funkcja tworząca i postać jawna ciągu

Post autor: PAV38 » 10 sie 2011, o 17:20

Tzn. rozumiem, że tak jest

Ale chodzi mi o moją metodę.
Patrząc na to tak teoretycznie:
Mam funkcję tworzącą, do której znajduję ciąg rekurencyjny. Ciąg ten na pewno odpowiada takiej funkcji, bo licząc A(x) postępuje wg. określonego schematu (tak jak np. dla ciągu Fibonacciego) no i chyba nie ma siły... skoro tam wychodzi, to tu też musi bo czym rożni się jedno od drugiego? A mając gotowy ciąg rekurencyjny, mamy znowu algorytm, który pozwala wyznaczyć jego postać jawną.

Nie upieram się, że to musi być dobrze, ale jeżeli nie jest, to po prostu chciałbym znać powód dlaczego? Bo patrząc tak logicznie, taka operacja byłaby wykonalna.

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Funkcja tworząca i postać jawna ciągu

Post autor: » 10 sie 2011, o 17:37

PAV38 pisze:\(\displaystyle{ 1+2x\sum_{n=1}^{+ \infty } a_{n}x^{n}-x^{2}\sum_{n=0}^{+ \infty }a_{n} x^{n}=1+2xA(x)-x^{2}A(x)}\)
Błąd jest tutaj - pierwsza suma to nie \(\displaystyle{ A(x)}\), lecz \(\displaystyle{ A(x)-1}\).

Twoja metoda jest poprawna, tylko przydługa. Równanie rekurencyjne w istocie można odgadnąć na podstawie mianownika funkcji, doprowadzając następnie do równości:
\(\displaystyle{ A(x)=a_0+a_1x+2x(A(x)-1)-x^2A(x)}\)
skąd łatwo odczytać \(\displaystyle{ a_0,a_1}\).

Ale to wszystko jest naokoło.

Q.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Funkcja tworząca i postać jawna ciągu

Post autor: PAV38 » 10 sie 2011, o 17:43

Czemu \(\displaystyle{ A(x)-1}\)??

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Funkcja tworząca i postać jawna ciągu

Post autor: » 10 sie 2011, o 17:47

\(\displaystyle{ \sum_{n=1}^{+ \infty } a_{n}x^{n}=\left( \sum_{n=0}^{+ \infty } a_{n}x^{n}\right) -a_0}\)

Q.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Funkcja tworząca i postać jawna ciągu

Post autor: PAV38 » 10 sie 2011, o 18:00

Hmm.. w takim razie jak wygląda wyprowadzenie wzoru na funkcję tworzącą ciągu Fibbonaciego?

Bo licząc, tak jak ten przykład zamiast:
\(\displaystyle{ \frac{x}{1-x-x^{2}}}\)
Wychodzi mi:
\(\displaystyle{ \frac{1}{1-x-x^{2}}}\)

I te iksy przez odjęcie \(\displaystyle{ a_{0}}\) ulegają redukcji.

EDIT:

Już wszystko się zgadza Robiłem błąd w liczeniu tej sumy Dziękuję za pomoc i przepraszam za upierdliwość
Ostatnio zmieniony 10 sie 2011, o 18:06 przez PAV38, łącznie zmieniany 1 raz.

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Funkcja tworząca i postać jawna ciągu

Post autor: » 10 sie 2011, o 18:04

Przecież w ciągu Fibonacciego \(\displaystyle{ f_0=0}\), więc odjęcie \(\displaystyle{ f_0}\) nic nie zmienia.

Q.

PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Funkcja tworząca i postać jawna ciągu

Post autor: PAV38 » 10 sie 2011, o 18:07

Tak, to ja źle sobie przepisałem warunek początkowy. Dziękuję za pomoc

janusz47
Użytkownik
Użytkownik
Posty: 6320
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 13 razy
Pomógł: 1362 razy

Funkcja tworząca i postać jawna ciągu

Post autor: janusz47 » 10 sie 2011, o 18:18

Dla Twojego ciągu rekurencyjnego funkcja tworząca ma postać:
\(\displaystyle{ A(x) = \sum_{n=0}^{\infty}a_{n}x^{n} = \sum_{n=0}^{\infty}(2a_{n-1} - a_{n-2})x^{n}= 1 + 2\sum_{n=1}^{\infty}a_{n-1}x^{n} - \sum_{n=0}^{\infty}a_{n-2}x^{n} = 1 + 2x \sum_{n=1}^{\infty}a_{n-1}x^{n-1}- x^2\sum_{n=0}^{\infty}a_{n-2}x^{n-2} = 1 +2xA(x) -x^2A(x).}\)
\(\displaystyle{ A(x)(1 -2x +x^2) = 1}\)
\(\displaystyle{ A(x) = \frac{1}{1 -2x +x^2} = \frac{1}{(x-1)^2} = \frac{1}{[-(1 - x)]^2};}\)
\(\displaystyle{ A(x) = \sum_{n=0}^{\infty}nx^{n}.}\)
Stąd wyraz ogólny ciągu:
\(\displaystyle{ a_{n} = n.}\)

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Funkcja tworząca i postać jawna ciągu

Post autor: » 10 sie 2011, o 19:45

Powyższe rachunki są nieprawidłowe.

Q.

ODPOWIEDZ