szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 sty 2018, o 16:31 
Użytkownik

Posty: 2
Lokalizacja: Ruda Slaska
Wyznaczyć postać zwartą ze względu na n dla rekurencji liniowej:
a_{0} = 0\\
a _{1} = 1\\
 a_{n}  = 5a _{n-1}  - 6 a_{n-2}
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 7 sty 2018, o 17:15 
Użytkownik
Avatar użytkownika

Posty: 11872
Lokalizacja: Wrocław
Metodą funkcji tworzących:
a_{n} = 5a _{n-1} - 6 a_{n-2}\\ \sum_{n=2}^{ \infty } a_n x^n=5x \sum_{n=2}^{ \infty }a_{n-1}x^{n-1}-6x^2 \sum_{n=2}^{ \infty }a_{n-2}x^{n-2}\\G(x)-a_1 x-a_0=5x\left( G(x)-a_0\right) -6x^2G(x)
Podstawiając a_0=0, \ a_1=1 otrzymujemy:
G(x)-x=(5x-6x^2)G(x)\\G(x)= \frac{x}{6x^2-5x+1} \ (*)
Dalej rozkładamy prawą stronę na ułamki proste i rozwijamy w szeregi geometryczne:
6x^2-5x+1=6\left( x-\frac{5}{12}\right)^2-\frac{6}{144}=6\left( x-\frac 1 3\right)\left(x-\frac 1 2 \right)\\
G(x)= \frac{A}{3\left(x-\frac 1 3\right)} + \frac{B}{2\left( x-\frac 1 2\right) }\\ G(x)=\frac{A}{3x-1}+\frac{B}{2x-1}
Sprowadzając po prawej do wspólnego mianownika i porównując otrzymany licznik z licznikiem po prawej stronie w (*), dostajemy, porównując współczynniki przy odpowiednich potęgach:
\begin{cases}2A+3B=1  \\  -A-B=0\end{cases}
Mnożąc drugie równanie stronami przez dwa i dodając do pierwszego, mamy B=1, zatem A=-1,
Czyli:
G(x)= \frac{1}{2x-1}-\frac{1}{3x-1}=- \frac{1}{1-2x}+ \frac{1}{1-3x}\\ G(x)= \sum_{n=0}^{ \infty }3^n x^n- \sum_{n=0}^{ \infty } 2^n x^n, \  |x|<\frac 1 3
Patrząc na współczynniki przy x^n w G(x), widzimy, że
a_n=3^n-2^n.
Góra
Kobieta Online
PostNapisane: 16 kwi 2018, o 19:07 
Użytkownik

Posty: 2
Lokalizacja: Katowice
Czy mógłbyś wytłumaczyć, jak z linijki
G(x) = \sum_{n=0}^{\infty} 3^n x^n  - \sum_{n=0}^{\infty} 2^n x^n
przeszedłeś do
a_n = 3^n - 2^n?
Czy to się jakoś "fachowo" nazywa? Powołałeś się na jakiś wzór?

Ps. Mam nadzieję, że wątek nie umarł... ;)
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2018, o 19:17 
Użytkownik
Avatar użytkownika

Posty: 11872
Lokalizacja: Wrocław
G(x) = \sum_{n=0}^{\infty} 3^n x^n - \sum_{n=0}^{\infty} 2^n x^n=\\= \sum_{n=0}^{ \infty } (3^n-2^n)x^n
No i dalej to jest kwestia definicji funkcji tworzącej. Funkcją tworzącą ciągu
(a_n)_{n\ge 0} jest właśnie \sum_{n=0}^{ \infty }a_n x^n.
(oczywiście ta suma zwykle nie zbiega dla dowolnego x, ale w rozważaniach związanych z funkcjami tworzącymi milcząco przyjmujemy, że operujemy wewnątrz przedziału zbieżności takiego szeregu potęgowego, wtedy też możemy różniczkować i całkować wyraz po wyrazie itd.).

Tak formalnie trzeba jeszcze wiedzieć, że funkcja tworząca jednoznacznie wyznacza ciąg, ale to się zwykle przyjmuje za znaną wiedzę (a wynika to chociażby z teorii dotyczącej szeregów Taylora).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 znajdź postać rekurencyjną ciągu (dyskretna)  gonti  1
 Funkcja tworząca i postać jawna ciągu  PAV38  18
 Postać jawna i ogólna - co to jest?  szymonides  3
 Wykorzystanie funkcji trygonometrycznych w rekurencji  Myterro  3
 Rozwiązywanie rekurencji - zadanie 3  pAULSG1  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl