Funkcja tworząca i postać jawna ciągu
-
- 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
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ć?
\(\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ć?
-
- Użytkownik
- Posty: 7917
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Funkcja tworząca i postać jawna ciągu
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.
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.
-
- 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
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.
Ja bym proponował zacząć od zróżniczkowania stronami równości:
\(\displaystyle{ \frac{1}{1-x}= \sum_{n=0}^{\infty}x^n}\)
Q.
-
- 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
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
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
-
- Użytkownik
- Posty: 7917
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Funkcja tworząca i postać jawna ciągu
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.}\)
\(\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.}\)
-
- 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
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.
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
- 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
Błąd jest tutaj - pierwsza suma to nie \(\displaystyle{ A(x)}\), lecz \(\displaystyle{ A(x)-1}\).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)}\)
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.
-
- 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
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ść
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
- Posty: 7917
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Funkcja tworząca i postać jawna ciągu
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.}\)
\(\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.}\)