rekurencja niejednorodna

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
M__
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 12 paź 2014, o 19:19
Płeć: Kobieta
Lokalizacja: Polska

rekurencja niejednorodna

Post autor: M__ »

Witam!
Mam podać wzór ogólny ciągu danego wzorem rekurencyjnym \(\displaystyle{ a_{n}=5a_{n-1}-6a_{n-2}+n3^{n} a_{1}=1 a_{2}=2}\)

Wyliczyłam, że dla rekurencji jednorodnej \(\displaystyle{ a_{n}=c_{1}2^{n}+c_{2}3^{n}}\) ale mam problem z rozwiązaniem szczególnym. Wiem, że dla \(\displaystyle{ n}\) rozwiązanie jest postaci \(\displaystyle{ c_{3}n+c_{4}}\) a dla \(\displaystyle{ 3^{n}}\) postaci \(\displaystyle{ c_{5}n3^{n}}\) ale nie wiem jak je teraz połączyć. Próbowałam to przemnożyć ale nic ciekawego nie wyszło..
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

rekurencja niejednorodna

Post autor: Mariusz M »

Ja takie rekurencje rozwiązuje z użyciem funkcji tworzącej
Tutaj przydatna będzie pochodna szeregu geometrycznego

Pochodna szeregu geometrycznego

\(\displaystyle{ \frac{\mbox{d}^k}{\mbox{d}x^k}\left(\frac{1}{1-qx}\right)=\frac{q^k\cdot k!}{\left(1-qx\right)^{k+1}}\\
\frac{\mbox{d}^k}{\mbox{d}x^k}\left(\sum_{n=0}^{\infty}{q^nx^n}\right)=q^{k}\sum_{n=0}^{\infty}{\prod_{i=1}^{k}{\left(n+i\right)}q^nx^n}\\
\frac{k!}{\left(1-qx\right)^{k+1}}=\sum_{n=0}^{\infty}{\prod_{i=1}^{k}{\left(n+i\right)}q^nx^n}}\)



\(\displaystyle{ a_{n}=5a_{n-1}-6a_{n-2}+n3^{n} a_{1}=1 a_{2}=2}\)



\(\displaystyle{ A\left( x\right)= \sum_{n=0}^{ \infty }a_{n}x^n\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=5\sum_{n=2}^{\infty}{a_{n-1}x^{n}}-6\sum_{n=2}^{ \infty }{a_{n-2}x^n}+ \sum_{n=2}^{ \infty }{n3^nx^n}\\
\sum_{n=0}^{ \infty }{3^nx^n}=\frac{1}{1-3x}\\
\frac{ \mbox{d}}{ \mbox{d}x }\left(\sum_{n=0}^{ \infty }{3^nx^n} \right)=\sum_{n=0}^{ \infty }{n3^nx^{n-1}} =\sum_{n=1}^{ \infty }{n3^nx^{n-1}}\\
= \sum_{n=0}^{ \infty }{\left( n+1\right) 3^{n+1}x^{n}} \\
\frac{ \mbox{d}}{ \mbox{d}x }\left( \frac{1}{1-3x} \right)= \frac{3}{\left( 1-3x\right)^2 } \\
\sum_{n=0}^{ \infty }{\left( n+1\right) 3^{n}x^{n}}= \frac{1}{\left( 1-3x\right)^2 }\\
\sum_{n=0}^{ \infty }{n3^{n}x^{n}}=\frac{1}{\left( 1-3x\right)^2 }-\frac{1}{1-3x}\\
\sum_{n=0}^{ \infty }{n3^{n}x^{n}}=\frac{3x}{\left( 1-3x\right)^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}}+\frac{3x}{\left( 1-3x\right)^2 }-3x\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=5x\sum_{n=1}^{\infty}{a_{n}x^{n}}-6x^2\sum_{n=0}^{ \infty }{a_{n}x^{n}}+\frac{3x}{\left( 1-3x\right)^2 }-3x\\
A\left( x\right)- \frac{7}{2}-x=5x\left( A\left( x\right) -\frac{7}{2}\right)-6x^2A\left( x\right)+ \frac{3x}{\left( 1-3x\right)^2 }-3x\\
A\left( x\right)\left( 1-5x+6x^2\right)= \frac{7}{2}+x- \frac{35}{2}x+\frac{3x}{\left( 1-3x\right)^2 } -3x\\
A\left( x\right)\left( 1-5x+6x^2\right)= \frac{7}{2}-\frac{39}{2}x+\frac{3x}{\left( 1-3x\right)^2 }\\
A\left( x\right)=-\frac{1}{2} \cdot \frac{39x-7}{\left( 1-5x+6x^2\right) } +\frac{3x}{\left( 1-3x\right)^2\left( 1-5x+6x^2\right) }\\
A\left( x\right)=-\frac{1}{2} \cdot \frac{39x-7}{\left( 1-2x\right)\left( 1-3x\right) }+\frac{3x}{\left( 1-2x\right)\left( 1-3x\right)^3 }\\
A\left( x\right)=\frac{a}{1-2x}+\frac{b}{1-3x}+ \frac{c}{\left( 1-3x\right)^2} +\frac{d}{\left( 1-3x\right)^3 }\\
A\left( x\right)=\frac{1}{2} \cdot \frac{1}{1-2x}+ \frac{9}{1-3x}- \frac{9}{\left( 1-3x\right)^2 }+\frac{3}{\left( 1-3x\right)^3 } \\
a_{n}= \frac{1}{2} \cdot 2^n+\left(9-9\left( n+1\right)+\frac{3}{2}\left( n+2\right)\left( n+1\right) \right) \cdot 3^n}\)
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

rekurencja niejednorodna

Post autor: yorgin »

mariuszm, brawo.

M__, niejednorodność jest postaci \(\displaystyle{ n3^n}\) oraz \(\displaystyle{ 3}\) jest jednym z pierwiastków wielomianu charakterystycznego, tj jest rozwiązaniem bazowym. Należy więc przewidywać rozwiązanie szczególne postaci

\(\displaystyle{ b_n=n(An+B)3^n}\).

Mogę Ci polecić ten temat: 140782.htm . Co prawda dotyczy on równań różniczkowych, jednak metody rozwiązywania są analogiczne. W szczególności metoda przewidywań jest analogiczna.
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

rekurencja niejednorodna

Post autor: Mariusz M »

yorgin, ja metody z równaniem charakterystycznym
nie lubię aż tak bardzo ponieważ jest ona dość ograniczona
(tak jak metoda przewidywania w równaniach różniczkowych
czy metoda współczynników oznaczonych przy całkowaniu)

Istnieje metoda analogiczna do uzmienniania stałych w równaniach różniczkowych
Mógłbyś ją opisać ? Kiedyś ją w sieci widziałem

Rozwiązując z użyciem funkcji tworzącej widać dlaczego należy tak a nie inaczej przewidywać
Funkcję tworzącą można zwinąć w szereg
korzystając z szeregu geometrycznego i jego pochodnych
(pochodne szeregu geometrycznego przydają się gdy czynniki mianownika są wielokrotne)
albo z dwumianu Newtona
Mnożenie funkcji tworzących to iloczyn Cauchyego szeregów

Kiedyś pokazywałeś użytkownikowi JakimPL dość ciekawy sposób rozwiązywania równań rekurencyjnych
Podałeś też literaturę ale w sieci nie znalazłem tej książki
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

rekurencja niejednorodna

Post autor: yorgin »

mariuszm, funkcje tworzące istotnie są dużo lepszym narzędziem, pozwalają poradzić sobie ze zdecydowanie szerszą klasą równań, szczególnie tych niejednorodnych. Jednak w prostych przypadkach poprzestańmy na przewidywaniu.
Istnieje metoda analogiczna do uzmienniania stałych w równaniach różniczkowych
Mógłbyś ją opisać ? Kiedyś ją w sieci widziałem
Niestety nie znam tej metody w sposób zadowalający. A internetu przepisywać nie ma sensu.
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

rekurencja niejednorodna

Post autor: Mariusz M »

Przy użyciu funkcji tworzących postać otrzymujemy z szeregów geometrycznych
W tej metodzie z równaniem charakterystycznym musimy założyć że rozwiązanie jest postaci \(\displaystyle{ \lambda^n}\)
Co z pierwiastkami wielokrotnymi ?
Jak wykazać że są takiej a nie innej postaci ?
Bez metody uzmienniania stałych nie wiadomo co zrobić z częścią niejednorodną
Przewidywanie nie jest zadowalającym sposobem

www.matematyka.pl/337734.htm#p5109399

Co z tą metodą ?
Nadawałaby się ona tutaj ?
Dla mnie im metoda bardziej ogólna tym lepsza
ODPOWIEDZ