Matematyka.pl

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ć?

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.

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

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.

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

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

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.

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.

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

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

Q.

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ść

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

Q.

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

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

Powyższe rachunki są nieprawidłowe.

Q.