szukanie zaawansowane
 [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 gru 2016, o 00:06 
Użytkownik

Posty: 4
Lokalizacja: Bytom
Witam,
Mam problem z zadaniem z książki pt. "Matematyka konkretna" (dokładniej 7.7, str 412 :-) .
Treść:
Rozwiąż równanie rekurencyjne
g_{0} =1 ;
g_{n}=g_{n-1}+2g_{n-2}+...+ng_{0} , dla n>0.

Mam to oprzeć o funkcje tworzące dla ciągu Fibonacciego, na tyle, na ile przejrzałem poszczególne rozdziały tej książki, plus przeglądałem to forum i wspomagałem się Google, rozumiem, że w tym przypadku nie mam do czynienia z klasycznym ciągiem Fibonacciego (gdzie byłoby to proste to obliczenia wg kroków przedstawionych w tej książce), ale ze splotem ciągów, czyli muszę wyznaczyć funkcję tworzącą zarówno dla ciągu F., jak i dla współczynnika zwielokrotniającego każde kolejne wyrażenie ciągu, dobrze myślę? Jakaś podpowiedź jak to zapisać i uzyskać postać zwartą ?
Dzięki!
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 1 gru 2016, o 12:13 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Według mnie jest to splot ciągów:

a_{n}=n

oraz:

b_{n}=b_{n-1}+b_{n-2}+...+b_{0}

ale funkcja tworząca dla b_{n} byłaby chyba koszmarna

chociarz jeśli przyjmiemy:

b_{0}=b_{1}=1

b_{2}=2,b_{3}=4

otrzymamy:

b_{n}=2^{n}

co już wygląda mniej koszmarnie


g(n)= \sum_{i=0}^{n-1}a_{n-i}b_{i}

jest to splot a funkcja tworząca splotu jest równa iloczynowi funkcji tworzących poszczególnych funkcji


Funkcja tworząca ciągu:

b_{n} , to:

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

Funkcja tworząca ciągu a_{n} to:

G(x)= \sum_{n=0}^{ \infty }nx^n=x \sum_{n=1}^{ \infty }nx^{n-1}=x\left(  \sum_{n=0}^{ \infty }x^n \right)'= x\left( \frac{1}{1-x}\right)'= \frac{x}{(1-x)^2}

F(x)=R(x)G(x)=\frac{1}{1-2x}  \cdot \frac{x}{(1-x)^2}

Te wszystkie granice sumowania mogłem pomieszać...

już lepiej ale nie najlepiej...
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 15:59 
Użytkownik

Posty: 4
Lokalizacja: Bytom
Dzięki, ale coś nie działa. Znalazłem w tej książce arkusz odpowiedzi, i tam napisali coś takiego:

G(z)=( \frac{z}{(1-z)^{2} })G(z)+1, stąd
G(z)= \frac{1-2z+z^{2}}{1-3z+z^{2}}=1+\frac{z}{1-3z+z^{2}}
i otrzymujemy g _{n} =F_{2n}+[n=0]

Teraz pytanie, o ile to rozumiem, to G(x) jest wyliczone poprawnie, natomiast coś nie tak jest w R(x) czyli w wyznaczeniu ciągu będącym tym odpowiadającym za narastanie współczynników przy bazowym wyrażeniu. Pytanie czy to nie będzie ciąg w postaci takiej, że tak jak mamy sumę poprzednich wyrazów ciągu, czyli kolejne wyrazy mają indeks (n-1), (n-2) itd, to czy nie ma odwrotnego narastania przy wyrazie czyli 1,2,3,...n, jak myślicie ?
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 16:30 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Właśnie może źle dobrałem ciąg narastający ale przyjąłem dwa początkowe wyrazy jeden i wtedy idzie mi to w kierunku ciągu geometrycznego ale nie będę się upierał.
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 16:39 
Użytkownik
Avatar użytkownika

Posty: 12427
Lokalizacja: czasem Warschau, czasem Breslau
Jeżeli mnie wzrok nie myli, to g_n jest splotem b_n=g_{n-1} z a_n=n.
To chyba powinno pomóc. :)

-- 2 gru 2016, o 15:41 --

No i dalej korzystamy z tego, że funkcja tworząca splotu to iloczyn funkcji tworzących.
Funkcja tworząca a_n=n jest trywialna do policzenia i nawet widać ją w rozwiązaniu.
Zastanów się proszę, jaka jest funkcja tworząca ciągu b_n=g_{n-1}, jeśli funkcją tworzącą
g_n jest G(x).
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 16:46 
Użytkownik

Posty: 4
Lokalizacja: Bytom
No właśnie a_{n}=n przy g_{0}, tutaj jest bardziej tak, że:
g_{n}=kg_{n-k}+(k+1)g_{n-(k+1)}+...ng_{0} ,
gdzie k=1
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 21:28 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Wiem , że jestem matoł ale to do mnie nie przemawia, że:

b_{n}=g_{n-1}

Bo według mnie dalej będziemy gonić w piętkę ciąg g_{n} zamiast definiować za pomocą dwóch ciągów różnych od niego definiujemy go za pomocą jego samego i dlatego się jakoś przeciw temu buntuję...

Ale może nie mam racji

Przejrzałem i widzę już co zrobiłem źle, lepiej późno niż później...
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2016, o 22:11 
Użytkownik
Avatar użytkownika

Posty: 12427
Lokalizacja: czasem Warschau, czasem Breslau
A może i nie mam racji? W sumie to ja miałem wrzesień z kombinatoryki kilka lat temu, więc pewnie żaden ze mnie autorytet w tej kwestii. To może rozpiszę:

g_{n}=g_{n-1}+2g_{n-2}+...+ng_{0}\\
 \sum_{n=1}^{ \infty }g_n x^n= \sum_{n=1}^{ \infty }\left( g_{n-1}+2g_{n-2}+...+ng_{0}\right)x^n\\ \sum_{n=1}^{ \infty }g_n  x^n= \sum_{n=1}^{ \infty } \sum_{k=0}^{n-1}(n-k)g_kx^n
Zmienimy kolejność sumowania po prawej stronie:
\sum_{n=1}^{ \infty }g_n x^n= \sum_{k=0}^{+\infty} \sum_{n=k+1}^{+\infty}(n-k)g_kx^n
Teraz w tej wewnętrznej sumie po prawej zmieńmy indeks na j=n-k:
\sum_{n=1}^{ \infty }g_n x^n= \sum_{k=0}^{+\infty} \sum_{j=1}^{+\infty}j g_{k}x^{j+k}= \sum_{k=0}^{+\infty}g_k x^k  \sum_{j=1}^{+\infty}j x^j
Oczywiście każde dziecko wie, że najlepszy serek owocowy jest i ma mleka wiele, a poza tym że
\sum_{j=1}^{+\infty}j x^j= \frac{x}{(1-x)^2} dla |x|<1 - zabawa z pochodnymi i różniczkowaniem szeregu potęgowego lub zmiana kolejności sumowania, nie będę tego rozpisywał.
Niech teraz G(x)= \sum_{n=0}^{+\infty}g_k x^k. Otrzymaliśmy, że
G(x)-1=G(x)  \cdot \frac{x}{(1-x)^2}, bo g_0=1,
a zatem G(x)= \frac{1}{1- \frac{x}{(1-x)^2} }= \frac{(1-x)^2}{x^2-3x+1}=1+ \frac{x}{x^2-3x+1} i ten ostatni ułamek należy rozwinąć w szereg potęgowy, a dostaniemy g_n.
Ale moim zdaniem to, że to jest splot odpowiednich ciągów, widać jak na dłoni, podobnie jak to, że Lech Wałęsa był agentem. Jeśli jednak widzicie tu błąd, to proszę o informację.
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2016, o 08:44 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Super zgadzam się w 100% otworzyłeś mi oczy miałem w tym zadaniu zaćmę.
łapka w górę...

-- 5 grudnia 2016, 10:01 --

Martwi mnie tylko, że Premislav jest głąbem matematycznym bo ja na miano głąba muszę w takim razie dopiero zasłużyć...Głąb matematyczny stoji na najniższym szczeblu drabiny matematycznej jednak jak widać są tacy co na tę drabinę jeszcze nie weszli.
Góra
Kobieta Offline
PostNapisane: 5 gru 2016, o 11:22 
Użytkownik
Avatar użytkownika

Posty: 663
Lokalizacja: Wrocław
johnnybsi napisał(a):
g_{0} =1 ;
g_{n}=g_{n-1}+2g_{n-2}+...+ng_{0} , dla n>0

Próbuję wypisać kilka pierwszych wyrazów tego ciągu i wychodzi mi:
g_o=1
g_1=g_o=1
g_2=g_1+2g_o=3
g_3=g_2+2g_1+3g_o=8
g_4=g_3+2g_2+3g_1+4g_o=21
g_5=g_4+2g_3+3g_2+4g_1+5g_o=55

czy ja dobrze to liczę?


Premislav napisał(a):
a zatem G(x)=\ ...\  =1+ \frac{x}{x^2-3x+1} i ten ostatni ułamek należy rozwinąć w szereg potęgowy, a dostaniemy g_n.

Rozwinęłam i otrzymałam
g_n=1+\frac{\sqrt5}{5}\left[\left(  \frac{3+\sqrt5}{2} \right) ^n-\left(  \frac{3-\sqrt5}{2} \right) ^n \right] \ \ \  \rightarrow  \begin{cases} g_o=1 \\ g_1=2\end{cases}\ \ \ ?
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2016, o 12:23 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Wniosek błąd w obliczeniach lub dobrana zła stała C
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2016, o 14:11 
Użytkownik
Avatar użytkownika

Posty: 12427
Lokalizacja: czasem Warschau, czasem Breslau
Ale "moja" funkcja tworząca zgadza się z odpowiedziami, więc gdyby to nie grało, to moglibyśmy dostać czek od Knutha za wskazanie błędu. :o [no chyba że to jakieś stare, niepoprawione wydanie] A mnie akurat brakuje trochę na prezenty.

Z uwagi na powyższe policzyłem więc też, choć na pierwszy rzut oka Twój wzór na n-ty wyraz wygląda OK :? :
G(x)=1+ \frac{x}{x^2-3x+1}=1+ \frac{A}{x-\frac 3 2-\frac{\sqrt{5}}{2}}+ \frac{B}{x-\frac 3 2+\frac{\sqrt{5}}{2}}\\ \begin{cases}A+B=1 \\ A\left( -\frac 3 2+\frac{\sqrt{5}}{2}\right)+B\left( -\frac 3 2-\frac{\sqrt{5}}{2}\right)=0  \end{cases}
Jeżeli teraz pomnożymy pierwsze równanie stronami przez-\frac 3 2+\frac{\sqrt{5}}{2}, po czym odejmiemy stronami drugie równanie od pierwszego, to otrzymamy
\sqrt{5}B=-\frac 3 2 +\frac{\sqrt{5}}{2} i analogicznie można wyliczyć, że \sqrt{5}A= \frac{3}{2}+ \frac{\sqrt{5}}{2}.
Ponadto dla dowolnej stałej a\neq 0 mamy \frac{1}{x-a}=- \frac{1}{a} \cdot   \frac{1}{1- \frac{x}{a} }, co dalej dla |x|<|a| można zapisać w postaci
-\frac 1 a \sum_{n=0}^{+\infty}\left( \frac x a\right)^n
Poza tym widzimy, że \frac{1}{\frac 3 2+\frac{\sqrt{5}}{2}}=\frac 3 2-\frac{\sqrt{5}}{2}
oraz, co oczywiście jest równoważne poprzedniemu stwierdzeniu, \frac{1}{\frac 3 2-\frac{\sqrt{5}}{2}}= \frac 3 2+\frac{\sqrt{5}}{2}.
Zbierając to do kupy, mamy:
G(x)=1+ \frac{x}{x^2-3x+1}=\\= \frac{1}{\sqrt{5}} (-\frac 3 2-\frac{\sqrt{5}}{2})\left( \frac 3 2-\frac{\sqrt{5}}{2}\right) \sum_{n=0}^{+\infty}\left(  \frac{3-\sqrt{5}}{2} \right)^n x^n+\frac{1}{\sqrt{5}} (-\frac 3 2-\frac{\sqrt{5}}{2})\left( -\frac 3 2+\frac{\sqrt{5}}{2}\right) \sum_{n=0}^{+\infty}\left(  \frac{3+\sqrt{5}}{2} \right)^nx^n,
a stąd g_n=\left[ n=0\right]- \frac{1}{\sqrt{5}}\left(\left(  \frac{3-\sqrt{5}}{2} \right)^n-\left(  \frac{3+\sqrt{5}}{2} \right)^n \right),
a to się zgadza z wynikiem użytkowniczki kinia7. Ale z tego spokojnie wychodzi g_1=1 oraz g_2=3, kinia7, czy nie dodawałaś cały czas jedynki do dalszych wyrazów, licząc ze wzoru otrzymanego po rozwinięciu w szereg potęgowy, zapominając o tym, że to tylko dla n=0?

-- 5 gru 2016, o 13:14 --

kinia7, już widzę, o co chodzi, jednak u Ciebie się nie zgadza z tą jedynką. No właśnie. Tej jedynki nie dodajesz do każdego wyrazu.
Zobacz, masz równość:

\sum_{n=0}^{ \infty } g_n x^n= 1+\sum_{n=0}^{ \infty }b_nx^n,
no to teraz widzimy, że przy 1 mamy wykładnik iksa równy zero. To zdefiniujmy sobie pomocniczy ciąg b_n', gdzie b_n'= \begin{cases} b_n+1 \text{ gdy } n=0 \\ b_n \text{ w przeciwnym razie }\end{cases}
Dostajemy wtedy g_n=b_n' dla każdego n, bo
\sum_{n=0}^{ \infty } g_n x^n= \sum_{n=0}^{ \infty } b_n' x^n
Mogłem to od razu zauważyć, zamiast pisać elaboraty na temat głupich równań i rozwijania w szereg (mnie to zajęło chyba ze 40 minut, bo z uwagi na moje ogólne nieogarnięcie sprawdzałem obliczenia po kilka razy, by mieć pewność). Fuck my life.

-- 5 gru 2016, o 13:20 --

Podsumowując: jestem głupi, bo nie zauważyłem od razu, w czym tkwił błąd w Twojej odpowiedzi, a kaski od Knutha na święta nie będzie. :mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen:
Góra
Kobieta Offline
PostNapisane: 5 gru 2016, o 18:59 
Użytkownik
Avatar użytkownika

Posty: 663
Lokalizacja: Wrocław
Premislav napisał(a):
... a to się zgadza z wynikiem użytkowniczki kinia7. Ale z tego spokojnie wychodzi g_1=1 oraz g_2=3, kinia7, czy nie dodawałaś cały czas jedynki do dalszych wyrazów, licząc ze wzoru otrzymanego po rozwinięciu w szereg potęgowy, zapominając o tym, że to tylko dla n=0?

Nie mogłam zapomnieć, bo nie wiedziałam tego. Dziękuję za naukę. Szkoda, że nie mogę Ci kliknąć „pomógł”.

nasze g_n to co drugi wyraz ciągu Fibonacciego
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2016, o 19:14 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Ja mu kliknę za Ciebie "pomógł".
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2016, o 19:18 
Użytkownik
Avatar użytkownika

Posty: 12427
Lokalizacja: czasem Warschau, czasem Breslau
To nie jest dla mnie aż takie istotne (choć przyznam, że lubię dostawać te punkty), ważne jest szczere podziękowanie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wykazać, że wyrazy ciągu zadanego rekurencją są ujemne  mck00  5
 Funkcje tworzace  P@wel  0
 Funkcje tworzące - sprawdzenie rozwiązania  krizzage  0
 Asymptotyka, funkcje wykładnicze  emperor2  2
 Rekurencja - wzór jawny  kheops  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl