Funkcja tworząca ciągu - podstawowe informacje

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

Witam.

Mam spore problemy z rozwiązywaniem zadań z funkcji tworzących, których nawet nie ruszyłem na zajęciach a trzeba je umieć.

Wziąłem sobie jakieś dowolne zadanie:

Wyznacz f. tworzącą ciągu:
\(\displaystyle{ a_{n}=n+1}\)
\(\displaystyle{ A(x)= \sum_{i=0}^{n} (n+1)x ^{n}}\)

Co teraz powinienem uzyskać z tego równania? Do jakiej postaci doprowadzić to równanie?

Jakby mi ktoś mógł napisać jakiś schemat, albo mniej więcej jak to się rozwiązuje.

Dziękuję i Pozdrawiam.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Premislav »

Czasem pomaga różniczkowanie i całkowanie wyraz po wyrazie (wewnątrz przedziału zbieżności możemy różniczkować i całkować szeregi potęgowe wyraz po wyrazie), a czasem np. zmiana kolejności sumowania. Jest też często używany fakt, że
\(\displaystyle{ \sum_{n=0}^{\infty}x^n=\frac{1}{1-x}}\) dla \(\displaystyle{ |x|<1}\)

Niepoprawnie zapisałeś funkcję tworzącą dla tego ciągu. Mamy dla \(\displaystyle{ a_n=n+1}\):
\(\displaystyle{ A(x)=\sum_{n=0}^{+\infty}a_n x^n=\sum_{n=0}^{+\infty}(n+1)x^n=\sum_{n=0}^{+\infty}(x^{n+1})'=\\=\left(\sum_{n=0}^{+\infty}x^{n+1} \right)'=\left(\frac {x}{1-x}\right)'=\frac{1}{(1-x)^2}}\)
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

A czy w przypadku takiego zadania:

\(\displaystyle{ a _{n}=nq ^{n}}\)
\(\displaystyle{ q \in R \setminus \left\{ 0\right\}}\)
\(\displaystyle{ A(x)=\sum_{n=0}^{+\infty} nq ^{n} x ^{n}=\sum_{n=0}^{+\infty} n(qx)^{n}=\sum_{n=0}^{+\infty}= \frac{qx}{(1-qx) ^{2}}}\)

Zastosowałem tutaj funkcję tworzącą dla ciągu \(\displaystyle{ a _{n}=n}\), czyli \(\displaystyle{ A(x)=\sum_{n=0}^{+\infty}nx ^{n} = \frac{x}{(1-x) ^{2} }}\)

Czy to jest poprawne?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Premislav »

Tak, jak najbardziej jest OK.
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

\(\displaystyle{ a _{n}=3 ^{n}+n2 ^{n}}\)
\(\displaystyle{ A(x)=\sum_{n=0}^{+\infty} (3 ^{n}+n2 ^{n}) x ^{n}=\sum_{n=0}^{+\infty} (3 ^{n}x ^{n})+\sum_{n=0}^{+\infty}(n2 ^{n} x ^{n})}=\sum_{n=0}^{+\infty} (3x) ^{n}+\sum_{n=0}^{+\infty}n(2x) ^{n}}= \frac{1}{1-3x}+ \frac{2x}{(1-2x) ^{2}}}\)

Poprawnie?

To to już mniej więcej rozumiem, a w jaki sposób wyznaczyć ciąg o podanej funkcji tworzącej np.

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

Tzn. mam teraz doprowadzić to równanie do takiej postaci, aby pojawiły się tam czynniki tj. \(\displaystyle{ \frac{1}{1-x}}\) etc.?

Innymi słowy zacząć od końca?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Premislav »

Dla \(\displaystyle{ a _{n}=3 ^{n}+n2 ^{n}}\) wyznaczyłeś funkcję tworzącą poprawnie.

Co do tego nowego, rozłóż
\(\displaystyle{ frac{x}{6x ^{2}-5x+1 }}\) na ułamki proste (jak nie wiesz, o co w tym chodzi, to zajrzyj może tu: 298450.htm) i dopasuj do wzorków, które już stosowałeś, tj.
\(\displaystyle{ sum_{n=0}^{ infty }(ax)^n=frac{1}{1-ax}\ sum_{n=0}^{ infty }n(ax)^n=frac{ax}{(1-ax)^2}}\)
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

Dobra, to Tym zajmę się jutro, a dziś jeszcze mam pytanie odnośnie wyznaczania funkcji tworzących.

Jeśli mam wyznaczyć f. tworzącą sumy dwóch ciągów przy czym określone są one następująco:

\(\displaystyle{ a _{n}=(-1) ^{n}}\)
\(\displaystyle{ b _{n}=\begin{cases} 1 &\text{dla } n =2k\\0 &\text{dla } n=2k+1 \end{cases}}\)

To mam osobno wykonać funkcję tworzącą dla wyrazów o indeksach parzystych i nieparzystych i na końcu zsumować? Tzn. W obydwóch przypadkach \(\displaystyle{ a _{n}}\) się nie zmienia, ale \(\displaystyle{ b _{n}}\) przyjmuje inną wartość.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Premislav »

No w sumie można tak powiedzieć. Wtedy funkcja tworząca \(\displaystyle{ (b_n)}\)
to \(\displaystyle{ \sum_{n=0}^{ \infty }x^{2n}}\)
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

Można to zapisać w ten sposób?

\(\displaystyle{ \sum_{n=0}^{ \infty }1x ^{n}+0x ^{n}}\)?

Tylko czemu w wykładniku jest \(\displaystyle{ 2}\)?

Czy dobrze myślę, że to zależy dla jakiego przedziału to jest? Tzn moje równanie po poprawie wyglądałoby tak:
\(\displaystyle{ \sum_{n=0}^{ \infty }1x ^{2n}+0x ^{n}}\)
albo
\(\displaystyle{ \sum_{n=0}^{ \infty }1x ^{2n}+0x ^{2n+1}}\)?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Premislav »

Można to zapisać w ten sposób?

\(\displaystyle{ \sum_{n=0}^{ \infty }1x ^{n}+0x ^{n}?}\)
Nie, to jest zupełnie źle. Funkcją tworzącą ciągu \(\displaystyle{ (b_n)}\) jest
\(\displaystyle{ \sum_{n=0}^{ \infty } b_n x^n}\)
Mamy \(\displaystyle{ b_0=1, b_1=0, b_2=1, b_3=0, b_4=1\dots}\) czyli przy jednomianach o potędze nieparzystej stoją współczynniki równe zero, a przy parzystych - jedynki. Stąd
funkcją tworzącą ciągu \(\displaystyle{ (b_n)}\) jest \(\displaystyle{ \sum_{n=0}^{ \infty }x^{2n}}\)
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

Ostatecznie:

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

Czy możliwy jest taki zapis?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Premislav »

Ja bym dodał jakieś nawiasy, w stylu
\(\displaystyle{ \sum_{n=0}^{ \infty }\left[(-x) ^{n} +x ^{2n}\right]}\),
a ponadto ostatnia równość nie jest prawdziwa, gdyż zazwyczaj
\(\displaystyle{ \sum_{n=0}^{ \infty } x^{2n} \neq \frac{1}{(1-x) ^{2}}}\)
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

Mógłbym prosić o jakąś podpowiedź co zrobić z \(\displaystyle{ x ^{2n}}\)?

Jeśli mamy np udowodnić, że \(\displaystyle{ B(x)=A(x) \cdot x}\)

\(\displaystyle{ b _{n}=\begin{cases} 0 &\text{dla } n =2k\\1 &\text{dla } n=2k+1 \end{cases}}\)
\(\displaystyle{ a _{n}=\begin{cases} 1 &\text{dla } n =2k\\0 &\text{dla } n=2k+1 \end{cases}}\)

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

Czy to jest poprawnie i czy trzeba dalej to rozwiązywać?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Premislav »

Mógłbym prosić o jakąś podpowiedź co zrobić z \(\displaystyle{ x ^{2n}}\)?
No to przecież proste jest.
\(\displaystyle{ x^{2n}=(x^2)^n}\) i wzór na sumę szeregu geometrycznego.

A to nowe zadanie zrobiłeś dobrze.
Warlok20
Użytkownik
Użytkownik
Posty: 509
Rejestracja: 1 paź 2011, o 16:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 156 razy
Pomógł: 3 razy

Re: Funkcja tworząca ciągu - podstawowe informacje

Post autor: Warlok20 »

Wyznaczyć ciąg o podanej funkcji tworzącej:

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

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

\(\displaystyle{ A=4}\)
\(\displaystyle{ B=-2}\)

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

\(\displaystyle{ a _{n}=4 \cdot 2 ^{n} -2}\)

Poprawnie rozwiązane?

Nie rozumiem pewnej kwestii, mianowicie:

\(\displaystyle{ A(x)= \frac{1}{(x- \frac{1}{2})(x-1)}}\)
I teraz musimy doprowadzić do postaci \(\displaystyle{ (1-qx)}\)

To wynikiem będzie:
\(\displaystyle{ \frac{1}{(1- 2x)(1-x)}}\)
Czy może
\(\displaystyle{ \frac{1}{2} \frac{1}{(1- 2x)(1-x)}}\) ?

Rozwiązując zadanie z bez \(\displaystyle{ \frac{1}{2}}\) wychodzi tak jak powinno, ale nie wiem czemu tam znika ta \(\displaystyle{ \frac{1}{2}}\)
ODPOWIEDZ