Rekurencje liniowe

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
bolt24
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 6 gru 2015, o 15:48
Płeć: Mężczyzna
Lokalizacja: Warszwa
Podziękował: 2 razy

Rekurencje liniowe

Post autor: bolt24 »

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

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

Nie wiem od czego mam zacząć. Za wszystkie odpowiedzi z góry dziękuję.
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Rekurencje liniowe

Post autor: Mariusz M »

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

\(\displaystyle{ 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}}\)
bolt24
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 6 gru 2015, o 15:48
Płeć: Mężczyzna
Lokalizacja: Warszwa
Podziękował: 2 razy

Rekurencje liniowe

Post autor: bolt24 »

Mam rozwiązanie przykładu a)

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

\(\displaystyle{ S_{n+1}= 2S_{n}+3S_{n-1}}\)

\(\displaystyle{ q^{n+1}= 2q^{n}+3q ^{n-1}}\)

\(\displaystyle{ q^{2}=2q+3}\)

\(\displaystyle{ q^{2}-2q-3=0}\)

\(\displaystyle{ \Delta=16}\)

\(\displaystyle{ \sqrt{\Delta}=4}\)

\(\displaystyle{ q _{1}=-1}\)

\(\displaystyle{ q_{2}=3}\)

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

\(\displaystyle{ S_{0}=1}\)

\(\displaystyle{ S_{1}=2}\)

\(\displaystyle{ \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}}\)
miodzio1988

Rekurencje liniowe

Post autor: miodzio1988 »

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


b) \(\displaystyle{ 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
bolt24
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 6 gru 2015, o 15:48
Płeć: Mężczyzna
Lokalizacja: Warszwa
Podziękował: 2 razy

Rekurencje liniowe

Post autor: bolt24 »

Chodziło mi o przykład a)
miodzio1988

Rekurencje liniowe

Post autor: miodzio1988 »

Jeżeli tego nie było w treści to tych warunków z innego miejsca nie weźmiesz
bolt24
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 6 gru 2015, o 15:48
Płeć: Mężczyzna
Lokalizacja: Warszwa
Podziękował: 2 razy

Rekurencje liniowe

Post autor: bolt24 »

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

Rekurencje liniowe

Post autor: miodzio1988 »

bolt24 pisze: \(\displaystyle{ S_{n+1}= 2S_{n}+3S_{n-1}}\)

\(\displaystyle{ q^{n+1}= 2q^{n}+3q ^{n-1}}\)

\(\displaystyle{ q^{2}=2q+3}\)

\(\displaystyle{ q^{2}-2q-3=0}\)

\(\displaystyle{ \Delta=16}\)

\(\displaystyle{ \sqrt{\Delta}=4}\)

\(\displaystyle{ q _{1}=-1}\)

\(\displaystyle{ q_{2}=3}\)

\(\displaystyle{ S_{n}= C_{1} \cdot(-1) ^{n}+ C_{2} \cdot 3^{n}}\)
tak
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Rekurencje liniowe

Post autor: Mariusz M »

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

\(\displaystyle{ 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 }\\}\)


\(\displaystyle{ \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 }\\}\)


\(\displaystyle{ 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}}\)
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Rekurencje liniowe

Post autor: a4karo »

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 \(\displaystyle{ 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 https://www.matematyka.pl/395260.htm#p5376195)
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Rekurencje liniowe

Post autor: Mariusz M »

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
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Rekurencje liniowe

Post autor: a4karo »

mariuszm pisze: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 ?
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ć...
ODPOWIEDZ