szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 cze 2017, o 17:50 
Użytkownik

Posty: 1
Lokalizacja: Gdansk
Dany jest ciąg rekurencyjny (a_{n}), w którym
a_{0} = 1

a _{1} = 2

a_{n} +  a_{n-1} - 6  a_{n-2} = 20 dla n \ge 2

Za pomocą funkcji tworzącej wyznacz jawny wzór na n-ty wyraz ciągu.

Czy ktoś byłby w stanie mi pomóc? Nie wiem jak się za to zabrać...
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 17 cze 2017, o 20:22 
Użytkownik
Avatar użytkownika

Posty: 11875
Lokalizacja: Wrocław
Przekształcamy:
a_n=-a_{n-1}+6a_{n-2}+20\\ \sum_{n=2}^{ \infty }a_n x^n= - \sum_{n=2}^{ \infty }a_{n-1}x^n+ 6\sum_{n=2}^{ \infty }a_{n-2}x^n +20 \sum_{n=2}^{ \infty }x^n\\\sum_{n=2}^{ \infty }a_n x^n= - x\sum_{n=2}^{ \infty }a_{n-1}x^{n-1}+ 6x^2\sum_{n=2}^{ \infty }a_{n-2}x^{n-2} +20 \sum_{n=2}^{ \infty }x^n
Oznaczmy teraz S(x)= \sum_{n=0}^{ \infty }a_n x^n
Wtedy mamy
\sum_{n=2}^{ \infty }a_n x^n=S(x)-a_1 x-a_0\\-x \sum_{n=2}^{ \infty }a_{n-1}x^{n-1}=-x\left(S(x)-a_0\right)\\  6x^2\sum_{n=2}^{ \infty }a_{n-2}x^{n-2}=6x^2 S(x)
Ponadto ze wzoru na sumę szeregu geometrycznego:
20 \sum_{n=2}^{ \infty }x^n= \frac{20x^2}{1-x}, \  |x|<1
Zbierając to do kupy, otrzymujemy
S(x)-a_1 x-a_0=-xS(x)+xa_0+6x^2S(x)+ \frac{20x^2}{1-x} \\ S(x)\left( 6x^2-x-1\right)=-x(a_0+a_1)-a_0- \frac{20x^2}{1-x}\\ S(x)=  \frac{-x(a_0+a_1)-a_0- \frac{20x^2}{1-x}}{6x^2-x-1}
Wstawiając a_0=1, a_1=2:
S(x)=  \frac{-3x-1- \frac{20x^2}{1-x}}{6x^2-x-1}= \frac{-3x+3x^2+x-1-20x^2}{(6x^2-x-1)(1-x)}= \frac{-17x^2-2x-1}{6(1-x)\left(x+\frac 1 3 \right)\left( x-\frac 1 2\right)  }\\S(x)= \frac{17x^2+2x+1}{(1-x)\left( 3x+1\right)\left( 1-2x\right)  }= \frac{A}{1-x}+ \frac{B}{1+3x } + \frac{C}{1-2x}
Czyli wykonujemy rozkład na ułamki proste:
298450.htm
A więc otrzymujemy układ równań
\begin{cases} -3C+2B-6A=17 \\2C-3B+A=2 \\C+B+A=1 \end{cases}
Rozwiąż go ulubioną metodą, wolfram twierdzi, że wychodzi tak:
https://www.wolframalpha.com/input/?i=solve+-3C%2B2B-6A%3D17+%262C-3B%2BA%3D2%26C%2BB%2BA%3D1
Potem rozwijasz poszczególne ułamki w szeregi potęgowe:
S(x)=A \sum_{n=0}^{ \infty }x^n+B \sum_{n=0}^{ \infty }(-3)^n x^n+C \sum_{n=0}^{ \infty } 2^n x^n
i a_n to jest współczynnik przy x^n, czyli:
a_n= -5+ (-3)^n+ 5 \cdot 2^n
Góra
Mężczyzna Offline
PostNapisane: 12 sie 2017, o 17:40 
Użytkownik

Posty: 25
Mam trochę inny przykład, ale postępując zgodnie ze wskazówkami trafiam pod koniec na ułamek, którego chyba(?) nie można rozbić na ułamki proste, czy ktoś może pomóc?
a _{0} = 1\\
a _{1} = 1\\
a _{n} = a _{n-1} - a _{n-2} \\

 \sum_{n=2}^{ \infty }  a _{n}x^{n} = x \sum_{n=2}^{ \infty } a _{n-1}x ^{n-1} - x ^{2} \sum_{n=2}^{ \infty } a _{n-2}x ^{n-2}\\
\\S(x) - a _{1}x - a _{0} = x(S(x) - a _{0}) - x ^{2}S(x) \\
\\ \frac{1}{x ^{2} - x + 1} = S(x)
Góra
Mężczyzna Offline
PostNapisane: 12 sie 2017, o 19:42 
Użytkownik
Avatar użytkownika

Posty: 11875
Lokalizacja: Wrocław
Obliczeń nie sprawdzałem, bo robię teraz inne zadanie, natomiast można sobie poradzić co najmniej na dwa sposoby:
1. Rozbić to całe \frac{1}{1-x+x^2} na ułamki proste zespolone.
2. Policzyć to zupełnie inaczej, zauważając, że dla n\ge 2 jest
a_n=a_{n-1}-a_{n-2}\\a_{n+1}=a_n-a_{n-1}
co po dodaniu stronami i skróceniu daje nam
a_{n+1}=-a_{n-2}, n \ge 2,
wystarczy jeszcze policzyć a_2=1 i dalej już łatwo napisać wzór na a_n...
Góra
Mężczyzna Offline
PostNapisane: 13 sie 2017, o 10:41 
Użytkownik

Posty: 25
Miałeś rację z tym, żeby liczyć na liczbach zespolonych tylko teraz nie jestem pewien jak policzyć A i B mając:
A \cdot  \left(  \frac{1}{2} +  \frac{ \sqrt{3} }{2}i \right)  + B \cdot  \left(  \frac{1}{2} -  \frac{ \sqrt{3} }{2}i \right)  = 1
Góra
Mężczyzna Offline
PostNapisane: 13 sie 2017, o 10:43 
Użytkownik
Avatar użytkownika

Posty: 1036
Lokalizacja: hrubielowo
Liczby zespolone z_1 i z_2 są równe tylko wtedy gdy \Re (z_1)=\Re (z_2) i \Im (z_1)=\Im (z_2) porównaj więc te liczby a dostaniesz układ 2 liniowych z 2 niewiadomymi A i B
Góra
Mężczyzna Offline
PostNapisane: 13 sie 2017, o 11:08 
Użytkownik

Posty: 25
Czyli wychodzi:
\begin{cases} A =  \frac{ \sqrt{3}i }{3}  \\ B = -\frac{ \sqrt{3}i }{3}  \end{cases}
jak to teraz wszystko poskładać, żeby otrzymać wzór jawny?
Góra
Mężczyzna Offline
PostNapisane: 13 sie 2017, o 17:42 
Użytkownik
Avatar użytkownika

Posty: 11875
Lokalizacja: Wrocław
Nie wiem, czy tyle wychodzi, wybacz, ale nie będę poświęcał czasu na sprawdzanie obliczeń, możesz to łacno sprawdzić na wolframalpha.com…
Generalnie, jak masz już takie liczby zespolone A, B, C, D, że
S(x)=\frac{1}{1-x+x^2}= \frac{A}{x-C}+ \frac{B}{x-D},
to rozwijasz te ułamki ze wzoru na sumę szeregu geometrycznego (przy odpowiednich założeniach),
tj.
\frac{A}{x-C}+ \frac{B}{x-D}  =- \frac{A}{C} \cdot  \frac{1}{1-\frac{1}{C} \cdot X}-  \frac{B}{D} \cdot  \frac{1}{1-\frac{1}{D}X}=\\= \sum_{n=0}^{ \infty }-AC^{-n-1}x^n+\sum_{n=0}^{ \infty }-BD^{-n-1}x^n=\\= \sum_{n=0}^{ \infty }\left(-AC^{-n-1}-BD^{-n-1} \right)x^n
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ciągi binarne a rekurencja  Anonymous  4
 rekurencja - podział prostokąta  nova  1
 Fraktale vel. rekurencja w trójkącie.  szampek  8
 Mały problem z funkcją tworzącą  kogutto  1
 zadanie - rekurencja  kishkash  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl