Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Rekurencje liniowe

Strona 1 z 1

[ Posty: 12 ]

Autor

Wiadomość

bolt24 Offline

Tytuł: Rekurencje liniowe

Napisane: 8 gru 2015, o 06:01

Posty: 17
Lokalizacja: Warszwa

Mam problem z rozwiązaniem następujących rekurencji liniowych:

a) $S_{n+1}=2S_{n}+3S_{n-1}$
b) $S_{n+1}=-2S_{n}-S _{n-1}, S_{0}=1, S_{1}=-3$
c) $S_{n+1= 3S_{n}-2S _{n-1}+ 2^{n}$

Nie wiem od czego mam zacząć. Za wszystkie odpowiedzi z góry dziękuję.

Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018

Góra

mariuszm Offline

Tytuł: Rekurencje liniowe

Napisane: 8 gru 2015, o 06:30

Posty: 6604
Lokalizacja: 53°02'N 18°35'E

Zdefiniuj sobie funkcję dla której współczynniki rozwinięcia w szereg potęgowy
będą kolejnymi wyrazami twojego ciągu

$S_{n+1}= 3S_{n}-2S _{n-1}+ 2^{n}\\ S_{n}=3S_{n-1}-2S_{n-2}+2^{n-1}\\ G\left( x\right)=\sum_{n=0}^{ \infty }{S_{n}x^{n}} \\ \sum_{n=2}^{ \infty }{S_{n}x^{n}}=3\sum_{n=2}^{ \infty }{S_{n-1}x^{n}}-2 \sum_{n=2}^{ \infty }{S_{n-2}x^{n}}+\frac{1}{2} \sum_{n=2}^{ \infty }{2^{n}x^{n}} \\ \sum_{n=2}^{ \infty }{S_{n}x^{n}}=3x\sum_{n=2}^{ \infty }{S_{n-1}x^{n-1}}-2x^2\sum_{n=2}^{ \infty }{S_{n-2}x^{n-2}}+ \frac{2x^2}{1-2x} \\ \sum_{n=2}^{ \infty }{S_{n}x^{n}}=3x\sum_{n=1}^{ \infty }{S_{n}x^{n}}-2x^2\sum_{n=1}^{ \infty }{S_{n}x^{n}}+\frac{2x^2}{1-2x}\\ \sum_{n=0}^{ \infty }{S_{n}x^{n}}-S_{0}-S_{1}x=3x\left( \sum_{n=0}^{ \infty }{S_{n}x^{n}}-S_{0}\right)-2x^2\sum_{n=1}^{ \infty }{S_{n}x^{n}}+\frac{2x^2}{1-2x}\\ G\left( x\right)-S_{0}-S_{1}x=3x\left( G\left( x\right)-S_{0} \right)-2x^2G\left( x\right) +\frac{2x^2}{1-2x}\\ G\left( x\right)-S_{0}-S_{1}x=3xG\left( x\right)-3xS_{0} -2x^2G\left( x\right) +\frac{2x^2}{1-2x}\\ G\left( x\right)-3xG\left( x\right)+2x^2G\left( x\right)=S_{0}+\left( S_{1}-3S_{0}\right)x+\frac{2x^2}{1-2x}\\ G\left( x\right)\left( 1-3x+2x^2\right)= \frac{2x^2+\left( S_{0}+\left( S_{1}-3S_{0}\right)x\right) \left( 1-2x\right) }{1-2x}\\ G\left( x\right)\left( 1-2x\right)\left( 1-x\right) = \frac{2x^2+\left( S_{0}+\left( S_{1}-3S_{0}\right)x\right) \left( 1-2x\right) }{1-2x}\\ G\left( x\right)=\frac{S_{0}-2S_{0}x+\left( S_{1}-3S_{0}\right)x-2\left( S_{1}-3S_{0}\right)x^2 +2x^2 }{\left( 1-2x\right)^2\left( 1-x\right) }\\ G\left( x\right)=\frac{2\left( 1-S_{1}+3S_{0}\right)x^2+\left( S_{1}-5S_{0}\right)x+S_{0} }{\left( 1-2x\right)^2\left( 1-x\right) } \\ G\left( x\right)= \frac{A}{1-2x}+\frac{B}{\left( 1-2x\right)^2 }+\frac{C}{1-x}$

Góra

bolt24 Offline

Tytuł: Rekurencje liniowe

Napisane: 11 gru 2015, o 14:19

Posty: 17
Lokalizacja: Warszwa

Mam rozwiązanie przykładu a)

Może mi ktoś powiedzieć z kąd się wzięło $S_{0}=1$ , $S_{1}=2$

$S_{n+1}= 2S_{n}+3S_{n-1}$

$q^{n+1}= 2q^{n}+3q ^{n-1}$

$q^{2}=2q+3$

$q^{2}-2q-3=0$

$\Delta=16$

$\sqrt{\Delta}=4$

$q _{1}=-1$

$q_{2}=3$

$S_{n}= C_{1} \cdot(-1) ^{n}+ C_{2} \cdot 3^{n}$

$S_{0}=1$

$S_{1}=2$

$\begin{cases}1=C _{1} \cdot (-1)^{0} + C_{2} \cdot 3^{0} } \\ 2= C_{1} \cdot (-1)^{1}+ C_{2} \cdot 3^{1} \end{cases}$

Góra

miodzio1988

Tytuł: Rekurencje liniowe

Napisane: 11 gru 2015, o 14:35

bolt24 napisał(a):

Mam problem z rozwiązaniem następujących rekurencji liniowych:

b) $S_{n+1}=-2S_{n}-S _{n-1}, S_{0}=1, S_{1}=-3$

Nie wiem od czego mam zacząć. Za wszystkie odpowiedzi z góry dziękuję.

Z treści zadania zapewne. Więc albo zła treść albo błędne rozwiązanie masz

Góra

bolt24 Offline

Tytuł: Rekurencje liniowe

Napisane: 11 gru 2015, o 14:38

Posty: 17
Lokalizacja: Warszwa

Chodziło mi o przykład a)

Góra

miodzio1988

Tytuł: Rekurencje liniowe

Napisane: 11 gru 2015, o 14:39

Jeżeli tego nie było w treści to tych warunków z innego miejsca nie weźmiesz

Góra

bolt24 Offline

Tytuł: Rekurencje liniowe

Napisane: 11 gru 2015, o 14:51

Posty: 17
Lokalizacja: Warszwa

A jak $S_{0}, S_{1}$ nie są znane, to jak powinno wyglądać rozwiązanie przykładu a)?

Góra

miodzio1988

Tytuł: Rekurencje liniowe

Napisane: 11 gru 2015, o 14:53

bolt24 napisał(a):

$S_{n+1}= 2S_{n}+3S_{n-1}$

$q^{n+1}= 2q^{n}+3q ^{n-1}$

$q^{2}=2q+3$

$q^{2}-2q-3=0$

$\Delta=16$

$\sqrt{\Delta}=4$

$q _{1}=-1$

$q_{2}=3$

$S_{n}= C_{1} \cdot(-1) ^{n}+ C_{2} \cdot 3^{n}$

tak

Góra

mariuszm Offline

Tytuł: Rekurencje liniowe

Napisane: 12 gru 2015, o 08:35

Posty: 6604
Lokalizacja: 53°02'N 18°35'E

Twój sposób jest dość ograniczony poza tym dużo w nim zapamiętywania bez uzasadnienia

W sposobie z mojego wcześniejszego wpisu każdy krok jest zrozumiały .
Wystarczy wstawić funkcję zdefiniowaną w postaci szeregu potęgowego
którego współczynnikami są kolejne wyrazy ciągu i równanie samo się rozwiązuje

Jeżeli funkcja ta okaże się funkcją wymierną to do wydobycia wyrazów ciągu
przydatne będą szeregi geometryczne i ich pochodne
Jeżeli funkcja ta nie będzie funkcją wymierną to przydatne będzie np policzenie pochodnej w zerze
i tutaj może być przydatny wzór Leibniza
jeżeli tylko uda nam się zgadnąć wzór na n. pochodną czynników

$S_{n+1}=-2S_{n}-S _{n-1}, S_{0}=1, S_{1}=-3\\ S_{n}=-2S_{n-1}-S_{n-2},S_{0}=1, S_{1}=-3\\ G\left( x\right)= \sum_{n=0}^{ \infty }{S_{n}x^{n}}\\ \sum_{n=2}^{ \infty }{S_{n}x^{n}}=-2\left( \sum_{n=2}^{ \infty }{S_{n-1}x^{n}}\right) - \left( \sum_{n=2}^{ \infty }{S_{n-2}x^{n}}\right) \\ \sum_{n=2}^{ \infty }{S_{n}x^{n}}=-2x\left( \sum_{n=2}^{ \infty }{S_{n-1}x^{n-1}}\right) - x^2\left( \sum_{n=2}^{ \infty }{S_{n-2}x^{n-2}}\right) \\ \sum_{n=2}^{ \infty }{S_{n}x^{n}}=-2x\left( \sum_{n=1}^{ \infty }{S_{n}x^{n}}\right) - x^2\left( \sum_{n=0}^{ \infty }{S_{n}x^{n}}\right) \\ \sum_{n=0}^{ \infty }{S_{n}x^{n}}-1+3x=-2x\left(\sum_{n=0}^{ \infty }{S_{n}x^{n}}-1 \right)-x^2\left(\sum_{n=0}^{ \infty }{S_{n}x^{n}} \right) \\ G\left( x\right)-1+3x=-2x\left( G\left( x\right)-1 \right)-x^2G\left( x\right)\\ G\left( x\right)-1+3x=-2x G\left( x\right)+2x -x^2G\left( x\right)\\ G\left( x\right)\left( 1+2x+x^2\right)=1-x\\ G\left( x\right)= \frac{1-x}{\left( 1+x\right)^2 }\\ G\left( x\right)= \frac{-1-x+2}{\left( 1+x\right)^2 }\\ G\left( x\right)=-\frac{1}{1+x}+\frac{2}{\left( 1+x\right)^2 }\\$

$\sum_{n=0}^{ \infty }{\left( -1\right)^nx^n }=\frac{1}{1+x}\\ \frac{ \mbox{d}}{ \mbox{d}x }\left(\sum_{n=0}^{ \infty }{\left( -1\right)^nx^n } \right) = \frac{ \mbox{d}}{ \mbox{d}x }\left( \frac{1}{ 1+x } \right) \\ \sum_{n=0}^{ \infty }{n\left( -1\right)^nx^{n-1} }=-\frac{1}{\left( 1+x\right)^2 }\\ \sum_{n=1}^{ \infty }{n\left( -1\right)^nx^{n-1} }=-\frac{1}{\left( 1+x\right)^2 }\\ \sum_{n=0}^{ \infty }{\left( n+1\right) \left( -1\right)^{n+1}x^{n} }=-\frac{1}{\left( 1+x\right)^2 }\\ \sum_{n=0}^{ \infty }{\left( n+1\right) \left( -1\right)^{n}x^{n} }=\frac{1}{\left( 1+x\right)^2 }\\$

$G\left( x\right)= \sum_{n=0}^{ \infty }{-\left( -1\right)^nx^n }+ \sum_{n=0}^{ \infty }{\left( n+1\right)\left( -1\right)^nx^n } \\ S_{n}=-\left( -1\right)^n+2\left( n+1\right)\left( -1\right)^n\\ S_{n}=\left( 2n+1\right)\left( -1\right)^{n}$

Góra

a4karo Offline

Tytuł: Rekurencje liniowe

Napisane: 12 gru 2015, o 12:47

Posty: 14748
Lokalizacja: Bydgoszcz

W powyższym poście autor próbuje przedstawić wykład "O wyższości Świąt Bożego Narodzenia nad Świętami Wielkiej Nocy" (czy ktos jeszcze pamięta ten cykl Jana Tadeusza Stanisławskiego).

Otóż każda metoda jest dobra, jeżeli prowadzi do oczekiwanych wyników. Jedni wola taką, inni wolą zapamiętać parę prostych wzorów. Niestety, uparte trzymanie się tej jednej jedynej prowadzi do rezultatów komicznych, jak np. rozwiązywanie rekurencji $a_n=-a_{n-1}$ metodą szeregów potęgowych (można, tylko jest to łapanie się za własny ogon: potrzebujesz wiedzy o ciągu geometrycznym, żeby stworzyć wzór opisujący ciąg geometryczny http://www.matematyka.pl/395260.htm#p5376195)

Góra

mariuszm Offline

Tytuł: Rekurencje liniowe

Napisane: 12 gru 2015, o 13:54

Posty: 6604
Lokalizacja: 53°02'N 18°35'E

Tylko że nauka na pamięć zwiększa prawdopodobieństwo że zapomnimy to czego się nauczyliśmy
no i z matematyki robimy przedmiot humanistyczny jak np język obcy

Mógłbyś uzasadnić postać rozwiązania z wielokrotnymi pierwiastkami
albo dlaczego tak a nie inaczej należy przewidywać rozwiązanie szczególne ?

Z tym rozwiązaniem szczególnym to tutaj także działa uzmiennianie stałych,
też rozwiązujemy układ równań tylko zamiast wyznacznika Wrońskiego
mamy wyznacznik Casoratiego a zamiast całkowania mamy sumowanie

Góra

a4karo Offline

Tytuł: Rekurencje liniowe

Napisane: 12 gru 2015, o 14:07

Posty: 14748
Lokalizacja: Bydgoszcz

mariuszm napisał(a):

Widziałeś kiedyś książeczkę Matematyka, poradnik encyklopedyczny, Bronsztejna?
Tam jest całe mnóstwo bardzo przydatnych informacji, których nikt nie uzasadnia: uzasadnieniami zajmowali się uczeni przez kilkaset ostatnich lat. W tej chwili jest to wiedza, której po prostu się używa.
Ktoś opanował wzory, ktoś opanował metodę.

Napisałem tylko tyle, że jedni wolą to, inni co innego i nie nam oceniać co dla kogoś jest łatwiejsze. A w rachunkach z szeregami banalnie łatwo się zamotać...

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 12 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
Rekurencje, funkcje tworzące	Teano	2
Funkcje tworzące,rekurencje,4zadania	jemcole	1
Rozwiąż rekurencję - zadanie 5	bartex9	0
Znajdź rekurencję dla ciągu	erym26	1
rownanie niejednorodne -rekurencje	superja	3

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]