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 »

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: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Funkcja tworząca i postać jawna ciągu

Post autor: janusz47 »

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 »

A mogę prosić o sprawdzenie poprawności mojego rozwiązania??
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

Funkcja tworząca i postać jawna ciągu

Post autor: »

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 »

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: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Funkcja tworząca i postać jawna ciągu

Post autor: janusz47 »

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 »

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.
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

Funkcja tworząca i postać jawna ciągu

Post autor: »

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 »

Czemu \(\displaystyle{ A(x)-1}\)??
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

Funkcja tworząca i postać jawna ciągu

Post autor: »

\(\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 »

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.
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

Funkcja tworząca i postać jawna ciągu

Post autor: »

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 »

Tak, to ja źle sobie przepisałem warunek początkowy. Dziękuję za pomoc
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Funkcja tworząca i postać jawna ciągu

Post autor: janusz47 »

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.}\)
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

Funkcja tworząca i postać jawna ciągu

Post autor: »

Powyższe rachunki są nieprawidłowe.

Q.
ODPOWIEDZ